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

Python 2.5 added the partition and rpartition methods for strings, but nothing similar for lists. These two functions provide that, with the addition of an optional key parameter with the same functionality as in itertools.groupby(.

Python, 64 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def partition(L, sep, key=None):
    """\
partition(list, sep, key) -> (head, sep, tail)

Search for the separator sep in list, and return the part before it,
the separator itself, and the part after it.  If the separator is not
found, return the list, None, and an empty list.

key specifies a function of one argument that is used to extract a
comparison key from each list element.

>>> for i in xrange(5):
...     print partition(range(4), i)
([], 0, [1, 2, 3])
([0], 1, [2, 3])
([0, 1], 2, [3])
([0, 1, 2], 3, [])
([0, 1, 2, 3], None, [])
"""
    if key:
        sep = key(sep)
        for i, item in enumerate(L):
            if sep == key(item):
                return L[:i], L[i], L[i+1:]
        return L, None, []
    else:
        try:
            i = L.index(sep)
            return L[:i], L[i], L[i+1:]
        except ValueError:
            return L, None, []

def rpartition(L, sep, key=None):
    """\
partition(list, sep, key) -> (head, sep, tail)

Search for the separator sep in list, starting at the end of list, and
return the part before it, the separator itself, and the part after
it.  If the separator is not found, return an empty list, None, and
the list.

key specifies a function of one argument that is used to extract a
comparison key from each list element.

>>> for i in xrange(5):
...     print rpartition(range(4), i)
([], 0, [1, 2, 3])
([0], 1, [2, 3])
([0, 1], 2, [3])
([0, 1, 2], 3, [])
([], None, [0, 1, 2, 3])
"""
    if not key:
        key = lambda x: x
    sep = key(sep)
    for i, item in enumerate(reversed(L)):
        if sep == key(item):
            i = len(L) - i - 1
            return L[:i], L[i], L[i+1:]
    return [], None, L

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Two external things would improve this recipe. First, an rindex method that finds the rightmost matching item in a list would allow rpartition to be as efficient as partition when no key function is used. Second, the addition of a key function to the index method would simplify the code considerable.

Created by Sam Denton on Wed, 30 Jan 2013 (MIT)
Python recipes (4591)
Sam Denton's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks