[Python-ideas] Function to unnest for-statements

May 23, 2008

      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.

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.

-- Carl Johnson