On 23 May 2008, at 08:15, Carl Johnson wrote:
This is based off of http://boredzo.org/blog/archives/2007-10-22/generating-all-combinations . It's also discussed at http://reddit.com/info/5ywrs/comments/ and someone with a lot of spare time can read Knuth's fascile on the subject at http://www-cs-faculty.stanford.edu/~knuth/fasc2a.ps.gz .
OK, suppose you have a situation where you need to loop through all combinations of 3 lists. The simple solution is to write three nested for-loops:
for x in xs: for y in ys: for z in zs: #Do something
Of course, this is obvious O(n^3), which is bad, but sometimes you don't have a choice. However, what if (to use an example I ran into), you're making up a truth table. If you know you have three variables, you might write:
for a in [True, False]: for b in [True, False]: for c in [True, False]: print a, b, c
Which yields
True True True True True False True False True True False False False True True False True False False False True False False False
But if you don't know how many variables you'll have, you're stuck writing a complicated function instead of using a nice, simple for- loop.
So, going back to the first example, wouldn't it be nicer to write:
for x, y, z in combine(xs, ys, zs): #Do something
If nothing else, this has the advantage that if you don't have to nest the for-loops, things don't end up being so deeply indented on the screen.
Similarly, a general truth table maker can be written:
ts_and_fs = [[True, False]] * num_vars for variables in combine(*ts_and_fs): print variables
So, I think a "combine" function (or some other, better name) would be a good thing to have, at least in the itertools, if not as a built-in function. How to implement it? Well, probably it should be done in C for efficiency, but of the versions done http://boredzo.org/blog/archives/2007-10-22/generating-all-combinations the one that I like best is
def combine(*sequences): #Test to guard against infinite recursion if sequences: def _inner(*seqs): if len(seqs) == 1: for i in seqs[0]: yield (i, ) else: for rest in combine(*seqs[:-1]): for i in seqs[-1]: yield rest + (i, ) return _inner(*sequences) else: #Empty generator that yields StopIteration def _inner(): return yield return _inner()
However, I'm also convinced that there is a more efficient way to do this'
I don't understand why you define those _inner() generator functions. Anyway, here's a version that doesn't use recursion: def product(*sequences): if not sequences: return i, imax = 0, len(sequences)-1 val = [None]*(imax+1) iters = [iter(seq) for seq in sequences] while i >= 0: for val[i] in iters[i]: if i == imax: yield tuple(val) else: i += 1 break else: iters[i] = iter(sequences[i]) i -= 1
So, what do you think? Is this a common enough need that it should be built into itertools? The main namespace? Or should we leave it out, since adding it would encourage people writing O(n^x) algorithms? If nothing else, list members can enjoy rewriting this function for fun.
It is already in itertools: Python 3.0a4+ (py3k:62388, Apr 19 2008, 15:34:00) [GCC 4.0.1 (Apple Inc. build 5465)] on darwin Type "help", "copyright", "credits" or "license" for more information.
from itertools import product for v in product(*[[True, False]]*3): ... print(v) ... (True, True, True) (True, True, False) (True, False, True) (True, False, False) (False, True, True) (False, True, False) (False, False, True) (False, False, False)
-- Arnaud