Distinct partitions of a sequence.
Python, 45 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | from itertools import chain, combinations
def partition(iterable, chain=chain, map=map):
s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
n = len(s)
first, middle, last = [0], range(1, n), [n]
getslice = s.__getslice__
return [map(getslice, chain(first, div), chain(div, last))
for i in range(n) for div in combinations(middle, i)]
>>> from pprint import pprint
>>> pprint(partition('abcdef'))
[['abcdef'],
['a', 'bcdef'],
['ab', 'cdef'],
['abc', 'def'],
['abcd', 'ef'],
['abcde', 'f'],
['a', 'b', 'cdef'],
['a', 'bc', 'def'],
['a', 'bcd', 'ef'],
['a', 'bcde', 'f'],
['ab', 'c', 'def'],
['ab', 'cd', 'ef'],
['ab', 'cde', 'f'],
['abc', 'd', 'ef'],
['abc', 'de', 'f'],
['abcd', 'e', 'f'],
['a', 'b', 'c', 'def'],
['a', 'b', 'cd', 'ef'],
['a', 'b', 'cde', 'f'],
['a', 'bc', 'd', 'ef'],
['a', 'bc', 'de', 'f'],
['a', 'bcd', 'e', 'f'],
['ab', 'c', 'd', 'ef'],
['ab', 'c', 'de', 'f'],
['ab', 'cd', 'e', 'f'],
['abc', 'd', 'e', 'f'],
['a', 'b', 'c', 'd', 'ef'],
['a', 'b', 'c', 'de', 'f'],
['a', 'b', 'cd', 'e', 'f'],
['a', 'bc', 'd', 'e', 'f'],
['ab', 'c', 'd', 'e', 'f'],
['a', 'b', 'c', 'd', 'e', 'f']]
|
Lovely, though I did have to unwrap the final list comprehension to figure out how it works!
I'm curious to know how you'd translate it into Python 3, when slices become part of standard item access? It seems this recipe wouldn't look quite so pretty.
I also wanted to know why partition allows clients to pass in chain and map?
Many thanks.