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.

Functions let you iterate multiple times (so you don't have to store the elements elsewhere). — Kelly Bundy, Jun 08 '22 at 05:38
I see. All generators in the questions are generator functions yielding an iterable. — jake77, Jun 08 '22 at 05:43
Why do you choose this way `generator` to make `powerset`? Just to learn or other User cases? — Daniel Hao, Jun 13 '22 at 19:22
@DanielHao it is a use case. Normally when iterating multiple iterables parallel e.g. with zip the iteration stops after the shortest iterable is exhausted. — jake77, Jun 20 '22 at 16:08
@DanielHao more importantly the generators provide elements by certain rules (all of the elements, only one of them, all combinations etc) so using a simple powerset was not possible — jake77, Jun 20 '22 at 19:09
@jake77 I see. What I saw it is the close similarity with this `powerset` post - https://stackoverflow.com/questions/68124242 <---- just change to `generator list`. — Daniel Hao, Jun 21 '22 at 15:50

Kelly Bundy · Accepted Answer · 2022-06-08T07:01:46.353

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]]

python combinations from lists

1 Answers1