Generating all tuples (Python)

From LiteratePrograms

Other implementations: Haskell | Lisp | Perl | Python | Ruby

This is a simple example of the tuples generation algorithm, written in Python.

see The Art of Computer Programming (TAOCP) Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005), ISBN 0-201-85393-0

Algorithm M

The generation function is genTuplesM as below:

Input parameter: we list the limits on each bit into a list as an input
Output: generating all possible tuples

<<genTuplesM.py>>=
def genTuplesM(lst):
  return reduce(lambda prev, b: [xs + [i] for xs in prev for i in range(1,b+1)], lst, [[]])
genTuplesM([3,5,3,2])

Alternatively, using product() in Python 2.6 and later:

<<genTuplesM2.py>>=
import itertools
def genTuplesM(lst):
  return itertools.product(*[range(1,b+1) for b in lst]) # returns an iterator
list(genTuplesM([3,5,3,2]))