So, I am considering various ways to calculate the Cartesian product of n arrays, and I came across a rather elegant solution (here on SO) to use the following code:
import itertools for array in itertools.product(*arrays): print array
Looking at the python document page (I use 2.7, battles) for itertools.product() , it says the code is equivalent to the following:
def product(*args, **kwds): # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 pools = map(tuple, args) * kwds.get('repeat', 1) result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod)
(He notices the following: this function is equivalent to the following code, except that the actual implementation does not create intermediate results in memory :)
I'm not a CS person, so I rather poorly evaluate the effectiveness of this algorithm. My first guess would be O(n^2) (due to a nested loop loop).
Am I really wrong?
source share