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

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
 ``` 1 2 3 4 5 6 7 8 9 10``` ```def getPerm(seq, index): "Returns the th permutation of " 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? Joel Neely 20 years, 8 months ago

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, 2 months ago

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)

### Required Modules

• (none specified)