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?