Welcome, guest | Sign In | My Account | Store | Cart
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']

History

  • revision 2 (15 years ago)
  • previous revisions are not available