[Python-ideas] Function to unnest for-statements

[Leif Walsh]

On Thu, 22 May 2008, Carl Johnson wrote:
> 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.

I think extra indentation helps, because it makes it clearer how the
loops nest, but I suppose you could do this if you really wanted;

>>> xs = ys = zs = [True, False]
>>> for a, b, c in [(x, y, z) for x in xs for y in ys for z in zs]:
...     print a, b, c
...
True True True
True True False
True False True
True False False
False True True
False True False
False False True
False False False
>>>

> 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've worked this out (I'm sure I did this in intro CS once before...),
although there is probably some optimization trick I'm missing, and
I'm probably doing some silly double-allocation thing or something.

>>> def combine(lists):
...     if len(lists) is 0:
...             return [[]]
...     first = combine(lists[0:-1])
...     total = []
...     for item in lists[-1]:
...             total += [[item] + subset for subset in first]
...     return total
...
>>> for set in combine([[True, False]] * 4):
...     print set
...
[True, True, True, True]
[True, True, True, False]
[True, True, False, True]
[True, True, False, False]
[True, False, True, True]
[True, False, True, False]
[True, False, False, True]
[True, False, False, False]
[False, True, True, True]
[False, True, True, False]
[False, True, False, True]
[False, True, False, False]
[False, False, True, True]
[False, False, True, False]
[False, False, False, True]
[False, False, False, False]
>>>

> 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.

I really, really don't think this is worth putting in any distributed
package, as it's a pretty simple thing to code up if you're careful.
That said, it _was_ a lot of fun rewriting it.  Thanks.  :D

-- 
Cheers,
Leif