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, 9 months ago  # | flag

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)
Python recipes (4591)
Raymond Hettinger's recipes (97)

Required Modules

  • (none specified)

Other Information and Tasks