python combinations from lists

Question

I have n generators in a list, each arbitrary length but none of them is empty.

lst = [gen_1, gen_2, ... gen_n]

I'd like to create the list A using the generators so that each element of A

• contains zero or one element from each generator
• all generators are exhausted when finsihing the creation of A

The content of A should be something like this:

gen_1[0]
.
.
gen_1[n]
gen_1[0], gen_2[0]
.
.
gen_1[n], gen_2[0]
.
.
gen_1[n], gen_2[m], ... gen_n[o]

In essence this is like creating the powerset using itertools.combinations (e.g. here), but we take zero to one element from each generator.

I imagine this would be solvable using recursion but can't wrap my head around it. Any help is appreciated.

Answer 1

Starting with the empty combination and then one by one consider each further generator and the combinations it contributes:

def gen_1():
    yield from 'ab'
def gen_2():
    yield from 'XY'
def gen_3():
    yield from [1, 2]
lst = [gen_1, gen_2, gen_3]

A = [[]]
for gen in lst:
    A += [a + [g]
          for a in A
          for g in gen()]

import pprint
pprint.pprint(A)

You could also swap the order of the list comprehension's two for clauses. Would likely be more efficient. I've done it the above way partly in order to somewhat use that they're generator functions and support multiple iterations.

Output (Try it online!):

[[],
 ['a'],
 ['b'],
 ['X'],
 ['Y'],
 ['a', 'X'],
 ['a', 'Y'],
 ['b', 'X'],
 ['b', 'Y'],
 [1],
 [2],
 ['a', 1],
 ['a', 2],
 ['b', 1],
 ['b', 2],
 ['X', 1],
 ['X', 2],
 ['Y', 1],
 ['Y', 2],
 ['a', 'X', 1],
 ['a', 'X', 2],
 ['a', 'Y', 1],
 ['a', 'Y', 2],
 ['b', 'X', 1],
 ['b', 'X', 2],
 ['b', 'Y', 1],
 ['b', 'Y', 2]]