8

I have a list of tuples, e.g: 

A=[(1,2,3), (3,5,7,9), (7)]

and want to generate all permutations with one item from each tuple.

1,3,7
1,5,7
1,7,7
...
3,9,7

I can have any number of tuples and a tuple can have any number of elements. And I can't use itertools.product() because python 2.5.

SilentGhost
  • 307,395
  • 66
  • 306
  • 293
lgwest
  • 1,347
  • 5
  • 16
  • 26
  • Note that you will need to redefine your A. When you say `A=[(1,2,3),(3,5,7,9),(7)]` the `(7)` at the end is evaluated as an integer, not a tuple. Therefore it's not iterable, and `product(*A)` will throw a TypeError. If you say `A=(1,2,3),(3,5,7,9),(7,)]` then `product(*A)` will work. – unutbu Nov 05 '09 at 15:57
  • Ok, I see, but this was a too simple example. I have A as a list of lists of 3-number tuples. But I want to remove the outer list and get A = lists of 3-number tuples. How do I do that? Better to make this a new beginner python question i think. – lgwest Nov 05 '09 at 22:23

4 Answers4

15

docs of itertools.product have an example of how to implement it in py2.5:

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)
SilentGhost
  • 307,395
  • 66
  • 306
  • 293
9
def product(*iterables):
    """ Equivalent of itertools.product for versions < 2.6,
        which does NOT build intermediate results.
        Omitted 'repeat' option.
        product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    """
    nIters = len(iterables)
    lstLenths = []
    lstRemaining = [1]
    for i in xrange(nIters-1,-1,-1):
        m = len(iterables[i])
        lstLenths.insert(0, m)
        lstRemaining.insert(0, m * lstRemaining[0])
    nProducts = lstRemaining.pop(0)

    for p in xrange(nProducts):
        lstVals = []

        for i in xrange(nIters):
            j = p/lstRemaining[i]%lstLenths[i]
            lstVals.append(iterables[i][j])
        yield tuple(lstVals)
Per L
  • 91
  • 1
  • 1
5

When playing around with generators, I too found a version of itertools.product, and it is almost as fast as the (native) library version, while being 100% compatible with it, and it does not build intermediate results:

def product(*args, **kwds):
    "Alternative fast implementation of product for python < 2.6"
    def cycle(values, uplevel):
        for prefix in uplevel:       # cycle through all upper levels
            for current in values:   # restart iteration of current level
                yield prefix + (current,)

    stack = (),             
    for level in tuple(map(tuple, args)) * kwds.get('repeat', 1):
        stack = cycle(level, stack)  # build stack of iterators
    return stack

With python 2.7.3, I found the performance to be really good (usually only about a factor of 5-10 slower with essentially the same memory usage).

>>> import itertools as itt
>>> timeit for _ in itt.product(range(20), range(3), range(150)): pass
1000 loops, best of 3: 221 µs per loop
>>> timeit for _ in product(range(20), range(3), range(150)): pass
1000 loops, best of 3: 1.14 ms per loop

EDIT: made code even simpler and Python 3-ready.

summentier
  • 456
  • 4
  • 13
  • Using a try/except to end a loop isn't great. You're basically relying on an error to short circuit your loop. – terry franguiadakis Aug 25 '17 at 22:58
  • 2
    I disagree with the accusation that I am abusing "error" conditions to exit the loop -- `StopIteration` is a valid condition to check for in a looping construct since it is internally used whenever a loop is terminated. Note that exceptions and `StopIteration` in particular have a slightly wider use in Python than in C++, cf. also the Zen of Python. – summentier Aug 28 '17 at 14:51
4

The itertools documentation contains full code showing what each function is equivalent to. The product implementation is here.

Daniel Roseman
  • 588,541
  • 66
  • 880
  • 895