Shuffling algorithm with no "self-mapping"?

Posted by OregonTrail on Programmers See other posts from Programmers or by OregonTrail
Published on 2013-11-12T17:50:06Z Indexed on 2013/11/12 22:03 UTC
Read the original article Hit count: 393

Filed under:
|
|

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[1])))

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[1])))

I'm currently writing a simulation with the following specifications for a shuffling algorithm:

  1. The algorithm is unbiased. If a true random number generator was used, no permutation would be more likely than any other.
  2. 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
  3. 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?

© Programmers or respective owner

Related posts about algorithms

Related posts about python