combinations of variable length nested lists

[Tim Peters]

[Mark Robinson]
> ...
> I have a nested list structure of the following format:
> [[2, 3, 4, 5],
>   [4, 5, 6, 7, 34],
>   [6, 2, 7, 4]
>   ....
>   ....
> ]
>
> I want to generate all possible combinations that take one element from
> each nested list
>
> i.e
> [2, 4, 6, ..., ...]
> [2, 4, 2, ..., ...]

You've seen many interesting approaches to this.  Cool!  Here's one for
brevity, but relying on 2.2:

from __future__ import generators
from test.test_generators import conjoin

alist = [[2, 3, 4, 5],
         [4, 5, 6, 7, 34],
         [6, 2, 7, 4]]

count = 0
for one in conjoin(map(lambda x: lambda: iter(x), alist)):
    count += 1
    if count < 6 or count > 75:
        print "%2d: %s" % (count, one)
    elif count == 6:
        print "..."

That prints:

 1: [2, 4, 6]
 2: [2, 4, 2]
 3: [2, 4, 7]
 4: [2, 4, 4]
 5: [2, 5, 6]
...
76: [5, 7, 4]
77: [5, 34, 6]
78: [5, 34, 2]
79: [5, 34, 7]
80: [5, 34, 4]

The "conjoin" imported there is a simple but general backtracking schema,
named in honor of Icon's "conjunction" operator.  It marches over all
cross-products of a list of no-argument functions that return iterators
(think that real fast 10 times <wink>), and generating a full cross-product
is the simplest thing you can do with it.  test_generators.py builds some
fancier things on top of it, and has 3 distinct implementations of conjoin()
(from purely recursive to purely iterative).

Since the implementation is generator-based, you don't have to compute all
the results at once:

>>> get = conjoin(map(lambda x: lambda: iter(x), alist)).next
>>> get()
[2, 4, 6]
>>> get()
[2, 4, 2]
>>> get()
[2, 4, 7]
>>> get()
[2, 4, 4]
>>> get()
[2, 5, 6]
>>>

Note that since "get" is also an iterator, nothing to stop you from feeding
it back into conjoin, either!  The disgusting possibilities are left to
sicker imaginations than mine.

cute-but-not-mandatory-ly y'rs  - tim