[Python-ideas] Function to unnest for-statements

[Arnaud Delobelle]

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