Why is my Cartesian product function not working?

Question

Consider the following function, the output of which is assumed to be the Cartesian product of a sequence of iterations:

def cart(*iterables): out = ((e,) for e in iterables[0]) for iterable in iterables[1:]: out = (e1 + (e2,) for e1 in out for e2 in iterable) return out 

Works great when the understanding of the generator is replaced by the understanding of lists. Also works when there are only 2 iterations. But when I try

 print(list(cart([1, 2, 3], 'ab', [4, 5]))) 

I get

 [(1, 4, 4), (1, 4, 5), (1, 5, 4), (1, 5, 5), (2, 4, 4), (2, 4, 5), (2, 5, 4), (2, 5, 5), (3, 4, 4), (3, 4, 5), (3, 5, 4), (3, 5, 5)] 

Why is this, and not a Cartesian product?

Answer 1

You create generator expressions that do not repeat until the next iteration of the for iterable in iterables[1:]: loop. They use closures that are viewed at runtime.

Generator expressions are essentially small functions in this regard, they create their own scope, and any names from the parent scope should be considered closures for this. A "function" is executed when you iterate, and only then is it necessary to close and enable the current value of the referenced variable.

So, you create one generator expression as follows:

 (e1 + (e2,) for e1 in out for e2 in iterable) 

where iterable is the closure taken from the parent scope (your local functions). But the search is not performed until the next iteration, when you execute a loop at what iterable next element in the sequence is.

So, to enter [1, 2, 3], 'ab', [4, 5] you create a generator expression with iterable = 'ab' , but by the time you actually iterate, the for loop has assigned a new value and now iterable = [4, 5] . When you finally iterate over the final (encoded) generator, only the most recent iterable assignment is taken into account.

You effectively create a product over iterables[0], iterables[-1] * len(iterables) - 1 ; iterables[1] to iterables[-2] skipped completely, all are replaced by iterables[-1] .

You can use the generator function to avoid the closure problem by passing iterable binding to local:

 def gen_step(out, iterable): for e1 in out: for e2 in iterable: yield e1 + (e2,) def cart(*iterables): out = ((e,) for e in iterables[0]) for iterable in iterables[1:]: out = gen_step(out, iterable) return out 

You can do the same with a lambda that returns a generator expression:

 def cart(*iterables): out = ((e,) for e in iterables[0]) for iterable in iterables[1:]: out = (lambda it=iterable: (e1 + (e2,) for e1 in out for e2 in it))() return out