To randomly shuffle an array, with no bias towards any particular permutation, there is the Knuth Fischer-Yeats algorithm. In Python:
#!/usr/bin/env python import sys from random import randrange def KFYShuffle(items): i = len(items) - 1 while i > 0: j = randrange(i+1) # 0 <= j <= i items[j], items[i] = items[i], items[j] i = i - 1 return items print KFYShuffle(range(int(sys.argv)))
There is also Sattolo's algorithm, which produces random cycles. In Python:
#!/usr/bin/env python import sys from random import randrange def SattoloShuffle(items): i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j] return items print SattoloShuffle(range(int(sys.argv)))
I'm currently writing a simulation with the following specifications for a shuffling algorithm:
- The algorithm is unbiased. If a true random number generator was used, no permutation would be more likely than any other.
- No number ends up at its original index. The input to the shuffle will always be A[i] = i for i from 0 to N-1
- Permutations are produced that are not cycles, but still meet specification 2.
The cycles produced by Sattolo's algorithm meet specification 2, but not specification 1 or 3. I've been working at creating an algorithm that meets these specifications, what I came up with was equivalent to Sattolo's algorithm.
Does anyone have an algorithm for this problem?