Welcome, guest | Sign In | My Account | Store | Cart

Distinct partitions of a sequence.

Python, 45 lines
 ``` 1 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']] ```

1 comment

Thomas Guest 14 years, 10 months ago

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.

 Created by Raymond Hettinger on Wed, 3 Jun 2009 (MIT)

Required Modules

• (none specified)