Programming challenge: wildcard exclusion in cartesian products

[Dinko Tenev]

Dinko Tenev wrote:
> Speculation: the time for
> building-up a smart structure to speed-up enumeration, together with
> the time for enumerating the set using that structure, should sum up to
> roughly Theta( n*|S^n| ), even with a really smart algorithm.

OK, maybe not.

This might be the worst case, looking at S^n - W only, but it's not
quite clear what "worst case" means in the context of concrete
implementations.  Surely, one can clog the program with zillions of
wildcards to test, so we can produce an arbitrarily "bad" case :) --
but such a case is obviously of little or no practical importance.  It
appears that, to make any sensible statements about performance in the
relevant cases, we have to take into account the size of the pattern
set used to specify W as well.

> [...] here's another speculation:
> such structure would likely take up Theta( |S^n| ) space in memory, in
> the worst case.

...and similarly for "worst case" here.

Cheers,

Dinko