Programming challenge: wildcard exclusion in cartesian products

Dinko Tenev dinko.tenev at gmail.com
Wed Mar 22 11:24:12 CET 2006


funkyj wrote:
> How about the other iterator characteristics?
>
> when there is a huge solution space can I ask the prolog version to
> give me the first 1000 solutions?

Geoffrey's post above offers one way to do this from within a REPL.

Within a program, as soon as you accept a solution, you're potentially
out of the "loop" (it is possible to use cut (!) to make this certain.)

>  The next 1000 solutions (i.e. 1000 - 1999)?

I am not quite sure how exactly you propose to do this in e.g. Python,
but if you mean to enumerate and skip over the first 1000 and then
continue with the rest, yes, this is also possible.

> If you can do that then it would appear that generators have no
> advantage over your prolog solution.

To be fair, the Python implementation has one significant advantage --
it offers reduced runtime complexity for quite a number of practical
cases (of course, this improvement is achievable in Prolog too,) though
I'm still inclined to think that it can be made to run in exponential
time.

Also, my Prolog version is non-compliant in that it treats a wildcard
as matching a single position, rather than matching any sequence.
Geoffrey's implementation does the right thing though.

Cheers,

Dinko




More information about the Python-list mailing list