CODEWITHSUNDEEP
python
Yevgen Yampolskiy
Yevgen Yampolskiy

Reputation: 7198

itertools.product pseudo-code

itertools documentation provides the following pseudo-code:

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)

map(tuple, args) looks redundant: could simply use args. Am I missing something?

Here is my test code (python 2.7):

def product2(*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 = 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)

print list (product(['A','B'],['C','D'])) == list (product2(['A','B'],['C','D']))
print list (product(['A','B'],['C','D'], repeat=2)) == list (product2(['A','B'],['C','D'], repeat=2))
print list (product([],[], repeat=2)) == list (product2([],[], repeat=2))
print list (product([])) == list (product2([]))

True

True

True

True

Upvotes: 0

Views: 570

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121962

Let's pass in iterators and see what happens:

>>> list(product(iter('AB'), iter('CD')))
[('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D')]
>>> list(product2(iter('AB'), iter('CD')))
[('A', 'C'), ('A', 'D')]
>>> list(product(iter('AB'), iter('CD'))) == list(product2(iter('AB'), iter('CD')))
False

Conclusion: you need to turn the arguments into tuples to capture all the values of the iterators.

It is even easier to illustrate when using only one iterator and the repeat option:

>>> list(product(iter('ABC'), repeat=2))
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
>>> list(product2(iter('ABC'), repeat=2))
[]

Upvotes: 4

Related Questions