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