Generating all combinations

Raymond Hettinger python at rcn.com
Wed Jun 3 22:21:36 EDT 2009


> What, no partitions?
>
> http://en.wikipedia.org/wiki/Partition_of_a_set

Seems like you could roll your own (using combinations as a starting
point):

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def partition(s):
    n = len(s)
    for i in range(n):
        for div in combinations(range(1,n), i):
            yield map(s.__getitem__, starmap(slice, pairwise(chain
([0], div, [n]))))

pprint(list(partition('abcd')))
[['abcd'],
 ['a', 'bcd'],
 ['ab', 'cd'],
 ['abc', 'd'],
 ['a', 'b', 'cd'],
 ['a', 'bc', 'd'],
 ['ab', 'c', 'd'],
 ['a', 'b', 'c', 'd']]



More information about the Python-list mailing list