Python and Combinatorics

[Peter Otten]

Nic wrote:

>> PS: Please don't top-post.

You probably overlooked that :-)

Here's a naive implementation:

from itertools import izip

def unique(items, N):
    assert N > 0
    if N == 1:
        for item in items:
            yield item,
    else:
        for index, item in enumerate(items):
            for rest in unique(items[index+1:], N-1):
                yield (item,) + rest

def repeat(*items):
    assert len(items)
    if len(items) == 1:
        for item in items[0]:
            yield item,
    else:
        for item in items[0]:
            for rest in repeat(*items[1:]):
                yield (item,) + rest

def render():
    pairs = list(unique(range(1, 4), 2))
    for item in unique(pairs, 3):
        for suffix in repeat(*["ab"]*3):
            yield tuple((a, b, s) for (a, b), s in izip(item, suffix))

if __name__ == "__main__":
    for item in render():
        print " ".join("%s%s%s" % t for t in item)

Peter