2

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?

  • Show us one of your algorithms that proved to be biased. I'm thinking that any algorithm that meets point 2 is biased by definition. – Robert Harvey Nov 12 '13 at 17:54
  • 1
    You may wish to read How We Learned to Cheat at Online Poker: A Study in Software Security which looked into a shuffle algorithm (amongst other things). "That means this shuffling algorithm never allows the 52nd card to end up in the 52nd place. This is an obvious, but easily correctable, violation of fairness." – user40980 Nov 12 '13 at 18:12
  • @RobertHarvey What I came up with, before looking up shuffling implementations, I've now noticed was equivalent to Sattolo's algorithm. It was KFY with retries. – OregonTrail Nov 12 '13 at 18:14
  • @RoberyHarvey, I've added a third specification now. – OregonTrail Nov 12 '13 at 18:24
  • @RobertHarvey In this context "unbiased" means that all allowed configurations are equally likely. Generating a random permutation and rejecting forbidden values produces such an unbiased configuration. For many problems this approach is prohibitively expensive, but in this case it is pretty fast. – CodesInChaos Nov 16 '13 at 14:38
8

By the way, a shuffling (permutation) that leaves no element in its original place is called a derangement.

A simple way is to just generate a random permutation, check to see if it's a derangement, and try again if it is not. The problem is that there is no upper bound on the time taken, but the expected number of shuffles is approximately e (2.718…), because the fraction of permutations that are also derangements approaches 1/e.

  • It seems so inefficient, but definitely meets all the requirements. I'll try shuffling with multiple threads. – OregonTrail Nov 14 '13 at 1:12
  • @OregonTrail As Derek said, on average it's only 2.7 times as expensive as Fisher-Yates, even without early-out. With early out, the overhead (approximately) halves, so it's only ~1.8 times as expensive. That's pretty efficient IMO. – CodesInChaos Nov 16 '13 at 14:36
  • What do you mean by "early-out"? – OregonTrail Nov 18 '13 at 8:07
  • Every time you fix a value, check straight away if you have failed to make a derangement, and if so return, rather than waiting until the end, and then checking the list. – Chris Jefferson Nov 25 '13 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.