This function, given a sequence and a number n as parameters, returns the <n>th permutation of the sequence (always as a list).
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?
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:
This can be corrected by revising the function as follows (using a helper which could have been in-lined):
With this replacement, the permutations are now in the expected order:
-jn-
not O(n) anymore. now it's O(n^2), because pop([i]) is linear