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']]
Created by Praveen on Sun, 17 Apr 2011 (MIT)
Python recipes (4591)
Praveen's recipes (2)

Required Modules

  • (none specified)

Other Information and Tasks