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

Getting <n>th permutation of a sequence (Python recipe) by Christos Georgiou
ActiveState Code (http://code.activestate.com/recipes/126037/)

This function, given a sequence and a number n as parameters, returns the <n>th permutation of the sequence (always as a list).

Python, 10 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def getPerm(seq, index):
    "Returns the <index>th permutation of <seq>"
    seqc= list(seq[:])
    seqn= [seqc.pop()]
    divider= 2 # divider is meant to be len(seqn)+1, just a bit faster
    while seqc:
        index, new_index= index//divider, index%divider
        seqn.insert(new_index, seqc.pop())
        divider+= 1
    return seqn

Its purpose was to be (relatively) quick and non-recursive (its execution time is O(N), for N=len(sequence) ). It doesn't check for duplicate items in the sequence, so a sequence has always n! different permutations (for n=len(sequence) ) Note that, due to Python's arbitrarily long integers, there are no out-of-range errors, so (for n=len(sequence) ) getPerm(seq, 0) == getPerm(seq, n!) == seq and getPerm(seq, -1) == getPerm(seq, n!-1)

PS Iff you can provide a "perfectly" random integer in the range 0...n!-1, then this function gives a "perfect" shuffle for the sequence. Perhaps progressively building a very large (much larger than n!-1) random number (given that the algorith actually uses the <index> % n! number) could give hope for a better randomness. Any thoughts?

Tags: algorithms

2 comments

Joel Neely 21 years, 3 months ago  # | flag

Not in lexicographic order... The recipe as posted doesn't return the index-th permutation in standard (lexicographic) order, as shown by the following snippet:

>>> for i in range (0, 6):
...     print i, getPerm ([1, 2, 3], i)
...
0 [1, 2, 3]
1 [1, 3, 2]
2 [2, 1, 3]
3 [3, 1, 2]
4 [2, 3, 1]
5 [3, 2, 1]

This can be corrected by revising the function as follows (using a helper which could have been in-lined):

def NPerms (seq):
    "computes the factorial of the length of "
    return reduce (lambda x, y: x * y, range (1, len (seq) + 1), 1)

def PermN (seq, index):
    "Returns the th permutation of  (in proper order)"
    seqc = list (seq [:])
    result = []
    fact = NPerms (seq)
    index %= fact
    while seqc:
        fact = fact / len (seqc)
        choice, index = index // fact, index % fact
        result += [seqc.pop (choice)]
    return result

With this replacement, the permutations are now in the expected order:

>>> for i in range (0, 6):
...     print i, PermN ([1, 2, 3], i)
...
0 [1, 2, 3]
1 [1, 3, 2]
2 [2, 1, 3]
3 [2, 3, 1]
4 [3, 1, 2]
5 [3, 2, 1]

-jn-

alex ... 16 years, 9 months ago  # | flag

not O(n) anymore. now it's O(n^2), because pop([i]) is linear

Created by Christos Georgiou on Fri, 10 May 2002 (PSF)
◄ Python recipes (4591) ►
◄ Christos Georgiou's recipes (6) ►

Required Modules

  • (none specified)

Other Information and Tasks