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

Permutations and combinations are often required in algorithms that do a complete search of the solution space. They are typically rather large so it's best not to compute them entirely but better to lazily generate them. This recipe uses Python 2.2 generators to create appropriate generator objects, that can be use for example as ranges in for loops.

Python, 62 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
#!/usr/bin/env python

__version__ = "1.0"

"""xpermutations.py
Generators for calculating a) the permutations of a sequence and
b) the combinations and selections of a number of elements from a
sequence. Uses Python 2.2 generators.

Similar solutions found also in comp.lang.python

Keywords: generator, combination, permutation, selection

See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66465
"""

from __future__ import generators

def xcombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xcombinations(items[:i]+items[i+1:],n-1):
                yield [items[i]]+cc

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc
            
def xselections(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for ss in xselections(items, n-1):
                yield [items[i]]+ss

def xpermutations(items):
    return xcombinations(items, len(items))

if __name__=="__main__":
    print "Permutations of 'love'"
    for p in xpermutations(['l','o','v','e']): print ''.join(p)

    print
    print "Combinations of 2 letters from 'love'"
    for c in xcombinations(['l','o','v','e'],2): print ''.join(c)

    print
    print "Unique Combinations of 2 letters from 'love'"
    for uc in xuniqueCombinations(['l','o','v','e'],2): print ''.join(uc)

    print
    print "Selections of 2 letters from 'love'"
    for s in xselections(['l','o','v','e'],2): print ''.join(s)

    print
    print map(''.join, list(xpermutations('done')))

This recipe provides both combinations and permutations and lazily generates them. You can do arbitrary calculations on the permutation/combination items not just print them.

If you require the complete list of permutations, just use the built-in list() operator. Note that the resulting list can be huge.

All x-generators defined here yield sequences with elements from the original sequence. Their difference is in which elements they take:

xpermutations takes all elements from the sequence, order matters.

xcombinations takes n distinct elements from the sequence, order matters.

xuniqueCombinations takes n distinct elements from the sequence, order is irrelevant.

xselections takes n elements (not necessarily distinct) from the sequence, order matters.

Note that 'distinct' means "different elements in the orginal sequence" and not "different value", i.e.

list(xuniqueCombinations('aabb',2)) is

[['a', 'a'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['a', 'b'], ['b', 'b']]

and not

[['a', 'b']].

If your sequence has only items with unique values, you won't notice the difference (no pun intended).

13 comments

Guy Argo 13 years, 11 months ago  # | flag

A simple refactoring. I notice that the bodies of xcombinations, xuniqueCombinations, xselections are almost identical. We could refactor as follows:

def generalized(f, items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)):
            for cc in generalized(f(items, i), n-1):
                yield [items[i]]+cc

def skipIthItem(items, i):
    return items[:i]+items[i+1:]

def afterIthItem(items, i):
    return items[i+1:]

def keepAllItems(items, i):
    return items

def xcombinations(items, n):
    return generalized(skipIthItem, items, n)

def xuniqueCombinations(items, n):
    return generalized(afterIthItem, items, n)

def xselections(items, n):
    return generalized(keepAllItems, items, n)
Li Daobing 12 years, 9 months ago  # | flag

A faster xuniqueCombinations algorithm.

def xuniqueCombinations(items, n):
    if n==0: yield []
    else:
        for i in xrange(len(items)-n+1):
            for cc in xuniqueCombinations(items[i+1:],n-1):
                yield [items[i]]+cc
Connelly Barnes 11 years, 3 months ago  # | flag

Faster permutations.

def permutations(L):
    if len(L) == 1:
        yield [L[0]]
    elif len(L) >= 2:
        (a, b) = (L[0:1], L[1:])
        for p in permutations(b):
            for i in range(len(p)+1):
                yield b[:i] + a + b[i:]

The above is 6x faster on my Pentium P3 3.0 GHz, Python 2.4.1.

Connelly Barnes 11 years, 3 months ago  # | flag

Appendum. I meant to say: 6x faster for computing list(permutations(range(8))).

Connelly Barnes 11 years, 2 months ago  # | flag

Err. On the last line that should have been yield p[:i] + a + p[i:] .

Simone Leo 10 years, 4 months ago  # | flag

much faster... ... But it only works on lists:

def permutations(L):
    if len(L) <= 1:
        yield L
    else:
        a = [L.pop(0)]
        for p in permutations(L):
            for i in range(len(p)+1):
                yield p[:i] + a + p[i:]
paul stadfeld 10 years ago  # | flag

Wrong terminology.

Unfortunately, it's a very poor example. The terminology is
all wrong.

"xpermutations takes all elements from the sequence, order matters."
This ought to be the Cartesian Product, but it's not (no replacement).

"xcombinations takes n distinct elements from the sequence, order
matters."
If order matters, it's a PERMUTATION, period.

"xuniqueCombinations takes n distinct elements from the sequence,
order is irrelevant."
No such thing, a Combination is unique by definition.

"xselections takes n elements (not necessarily distinct) from the
sequence, order matters."
Ah, this allows a size operator, so if size = length, we get full
Cartesian Product.

The proper terminology for the Cartesian Product and
its subsets is:

Permutations with replacement
Combinations with replacement
Permutations without replacement
Combinations without replacement

And if the functions were properly labeled, you would get:

    permutation without replacement - size 4

Permutations of 'love'
love loev lvoe lveo leov levo olve olev ovle ovel oelv oevl vloe vleo
vole voel velo veol elov elvo eolv eovl evlo evol


    permutation without replacement - size 2

Combinations of 2 letters from 'love'
lo lv le ol ov oe vl vo ve el eo ev


    combination without replacement - size 2

Unique Combinations of 2 letters from 'love'
lo lv le ov oe ve


    permutation with replacement - size 2

Selections of 2 letters from 'love'
ll lo lv le ol oo ov oe vl vo vv ve el eo ev ee


    full Cartesian Product, permutations with replacement - size 4

Selections of 4 letters from 'love'
llll lllo lllv llle llol lloo llov lloe llvl llvo llvv llve llel lleo
llev llee loll lolo lolv lole lool looo loov looe lovl lovo lovv love
loel loeo loev loee lvll lvlo lvlv lvle lvol lvoo lvov lvoe lvvl lvvo
lvvv lvve lvel lveo lvev lvee lell lelo lelv lele leol leoo leov leoe
levl levo levv leve leel leeo leev leee olll ollo ollv olle olol oloo
olov oloe olvl olvo olvv olve olel oleo olev olee ooll oolo oolv oole
oool oooo ooov oooe oovl oovo oovv oove ooel ooeo ooev ooee ovll ovlo
ovlv ovle ovol ovoo ovov ovoe ovvl ovvo ovvv ovve ovel oveo ovev ovee
oell oelo oelv oele oeol oeoo oeov oeoe oevl oevo oevv oeve oeel oeeo
oeev oeee vlll vllo vllv vlle vlol vloo vlov vloe vlvl vlvo vlvv vlve
vlel vleo vlev vlee voll volo volv vole vool vooo voov vooe vovl vovo
vovv vove voel voeo voev voee vvll vvlo vvlv vvle vvol vvoo vvov vvoe
vvvl vvvo vvvv vvve vvel vveo vvev vvee vell velo velv vele veol veoo
veov veoe vevl vevo vevv veve veel veeo veev veee elll ello ellv elle
elol eloo elov eloe elvl elvo elvv elve elel eleo elev elee eoll eolo
eolv eole eool eooo eoov eooe eovl eovo eovv eove eoel eoeo eoev eoee

(comment continued...)

paul stadfeld 10 years ago  # | flag

(...continued from previous comment)

evll evlo evlv evle evol evoo evov evoe evvl evvo evvv evve evel eveo
evev evee eell eelo eelv eele eeol eeoo eeov eeoe eevl eevo eevv eeve
eeel eeeo eeev eeee


And Combinations with replacement seems to be missing.
Benjamin Sergeant 8 years, 11 months ago  # | flag

Comment number 4 code is not working for S = [0,1,2,3]. Comment number 6 code works.

Christopher Smith 7 years, 5 months ago  # | flag

Regarding comment 8 noting the lack of Combination with Replacement: here is a version which (without recursion for the "replacement" case) returns a generator giving the k-sized subsets of a set and allows for combinations with replacement. (It's part of my work with sympy at branch 1766 at github under acct smichr):

def subsets(seq, k, repetition=False):
    """Generates all k-subsets (combinations) from an n-element set, seq.
           >>> list(subsets([1,2], 2))
           [[1, 2]]
           >>> list(subsets([1, 2, 3], 2))
           [[1, 2], [1, 3], [2, 3]]

       subsets(seq, k, repetition=True) will return the (n-1+k)!/k!/(n-1)!
       combinations *with* repetition:
           >>> list(subsets([1,2], 2, repetition=True))
           [[1, 1], [1, 2], [2, 2]]

       If you ask for more items than are in the set you get the empty set
       unless you allow repetitions (i.e. replacement of what you took
       from the set):
           >>> list(subsets([0,1], 3, repetition=False))
           []
           >>> list(subsets([0,1], 3, repetition=True))
           [[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
       """

    if k == 0:
        yield []
    else:
        if not repetition:
            for i in xrange(len(seq)):
                for cc in subsets(seq[i+1:], k-1, False):
                    yield [seq[i]]+cc
        else:
            nmax = len(seq) - 1
            indices = [0] * k
            yield seq[:1] * k
            while 1:
                indices[-1] += 1
                if indices[-1] > nmax:
                    #find first digit that can be incremented
                    for j in range(-2, -k-1, -1):
                        if indices[j] < nmax:
                            indices[j:] = [indices[j] + 1] * -j
                            break # increment and copy to the right
                    else:
                        break # we didn't for-break so we are done
                yield [seq[li] for li in indices]

There is also a discussion of these issues at http://coding.derkeiler.com/Archive/Python/comp.lang.python/2008-07/msg02095.html but I have not been able to duplicate the results and obtain similar times with what is presented. I'm not sure if I'm doing something wrong or if my machine is just that much slower.

Amin Abbaspour 6 years, 1 month ago  # | flag

For faster permutation similar to what Connelly and Simone recommended but for a length less than len(L) (i.e. P(L,r)) can try this:

def fast_permutation(L, n):
    if n == 1:
        for l in L:
            yield [l]
    else:
        a = [L.pop(0)]
        for p in fast_permutation(L, n-1):
            for i in range(n):
                yield p[:i] + a + p[i:]
        if len(L) >= n:
            for p in fast_permutation(L, n):
                yield p

And this is the same code which returns tuples:

def fast_permutation_tuple(L, n):
    if n == 1:
        for l in L:
            yield (l,)
    else:
        a = (L.pop(0),)
        for p in fast_permutation_tuple(L, n-1):
            for i in range(n):
                yield p[:i] + a + p[i:]
        if len(L) >= n:
            for p in fast_permutation_tuple(L, n):
                yield p

This way you can check the results with itertools.permutations() like:

input = range(3)
r = 2
result = fast_permutation_tuple(input, r)
expected = itertools.permutations(input, r)
result.sort()
expected.sort()
self.assertEquals(result, expected)
Amin Abbaspour 6 years, 1 month ago  # | flag

A comparison plot is available here.

Ruben Decrop 6 years, 1 month ago  # | flag

I use the following algorithm for permutations:

def gperm(it, r=None): 
    x = list(it) 
    n = len(x) 
    r = n if r is None else r 
    if r>n: 
        return 
    if r==1: 
        for i in x: 
            yield [i] 
    elif r>1: 
        el, rest = x[0], x[1:] 
        for c in gperm(rest, r-1): 
            c.insert(0,el) 
            yield c 
        for j in range(n-1): 
            el, rest[j] = rest[j], el 
            for c in gperm(rest, r-1): 
                c.insert(0,el) 
                yield c

The algorithm is not as fast as the fast_permutation, but it is faster than the orginal one and than the pure python one available in test_itertools. The main advantage of this code is that the all permutations are generated in logical order: all permutations that starts with the first element come first. This is not the case with fast_permutation. This characteristic is essential to a backtracking problem I have. In fact I have a second version with a additional pruning function reducing the number of permutations generated. The ix parameter indicates which element in the permutation is tested

def gperm2(it, r=None, pruningf=None, ix=0): 
     x = list(it)
     n = len(x) 
     r = n if r is None else r 
     if r>n: 
         return 
     if r==1: 
         for i in x: 
             if not pruningf or pruningf(i, ix): 
                  yield [i] 
     elif r>1: 
          el, rest = x[0], x[1:] 
          if not pruningf or pruningf(el, ix): 
              for c in gperm2(rest, r-1, pruningf, ix+1): 
                  c.insert(0,el) 
                  yield c 
          for j in range(n-1): 
              el, rest[j] = rest[j], 
              el if not pruningf or pruningf(el,ix): 
                  for c in gperm2(rest, r-1, pruningf, ix+1): 
                      c.insert(0,el) 
                      yield c

Because the permutations are generated in logical order, the pruning function is much more optimal to cut away unnecessary permutations before they are generated. As a consequence for backtracking applications, this algorithm is faster than fast_permutation

Add a comment

Sign in to comment