ActiveState Code

Recipe 126037: Getting <n>th permutation of a sequence

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

Python 
 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

Discussion

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?

Comments

  1. 1. At 9:13 p.m. on 12 jan 2003, Joel Neely said:

    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-

  2. 2. At 3:41 a.m. on 3 jul 2007, alex ... said:

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

Sign in to comment