from itertools import islice, repeat, izip, cycle # If PEP 3102 is accepted, the signature would be #def iterCombinations(*iterables, blocksize=1): def iterCombinations(*iterables, **kwds): '''Generates the combinations of the given iterables. @returns: An iterator over all combinations of the C{iterables}. Each yielded combination is a list of size C{len(iterables)} where the i-th element is drawn from the i-th iterable. B{Important note:} This list should not be modified between iterations; if you need to modify it, copy it to a new container. @param iterables: One or more arbitrary iterables. @param kwds: Currently only 'blocksize' allowed. @keyword blocksize: Determines the order of the yielded combinations. By default (C{blocksize=1}), the first iterable corresponds to the most outer loop (slowest change) and the last iterable corresponds to the most inner loop (fastest change). For larger blocksize, each iterable is first partitioned into consecutive blocks of size C{blocksize} (except perhaps for the last block which may be shorter). Then each combination is yielded by first iterating over each block combination C{B := (B1,B2,..Bn)} and then yielding each combination from B. More generally, C{blocksize} can be an iterable so that different C{iterables} can be partitioned by different block size. In this case, C{blocksize} is repeated as many time as necessary to match C{len(iterables)}. For instance:: iterCombinations(range(4),range(6),range(8),'xyz', blocksize=(2,3)) partitions C{range(4)} and C{range(8)} with blocksize=2, while C{range(6)} and 'xyz' are partitioned with blocksize=3. ''' combo = [None] * len(iterables) blocksize = kwds.get('blocksize', 1) if isinstance(blocksize, int): sizes = repeat(blocksize) else: sizes = cycle(iter(blocksize)) block_lists = [list(_iterblocks(it,sz)) for it,sz in izip(iterables,sizes)] for block_combo in _iterCombinations(block_lists, [None] * len(iterables)): for _ in _iterCombinations(block_combo, combo): yield combo def _iterCombinations(groups, combo_list, index=0): # generate recursively all combinations of groups, updating combo_list # *in-place* for each combination. if index < len(groups)-1: for x in groups[index]: combo_list[index] = x for _ in _iterCombinations(groups,combo_list,index+1): yield combo_list else: # optimization to avoid the last level of recursion assert index == len(groups)-1 for x in groups[index]: combo_list[index] = x yield combo_list def _iterblocks(iterable, blocksize, factory=tuple): # split the iterable into blocks of blocksize iterable = iter(iterable) while True: block = factory(islice(iterable,blocksize)) if not block: break yield block if len(block) < blocksize: break # example >>> for c in iterCombinations(range(5), 'abc'): print c ... [0, 'a'] [0, 'b'] [0, 'c'] [1, 'a'] [1, 'b'] [1, 'c'] [2, 'a'] [2, 'b'] [2, 'c'] [3, 'a'] [3, 'b'] [3, 'c'] [4, 'a'] [4, 'b'] [4, 'c'] >>> for c in iterCombinations(range(5), 'abc', blocksize=2): print c ... [0, 'a'] [0, 'b'] [1, 'a'] [1, 'b'] [0, 'c'] [1, 'c'] [2, 'a'] [2, 'b'] [3, 'a'] [3, 'b'] [2, 'c'] [3, 'c'] [4, 'a'] [4, 'b'] [4, 'c']