Hacker News Reader

Comment by drawfloat | Hacker News Reader

I've definitely done this before, though mainly in non-critical situations (eg: shuffling a bunch of product images to display on a screen in store) where I didn't care too much if it wasn't TRUE shuffling.

Is there a name for this approach/any info on why it doesn't work?

View on HN

An easy argument why it cannot work: consider an array with 3 elements, [a,b,c]. “Shuffling” it could look as follows.

    Step 1. Swap a, c -> [c,b,a]
    Step 2. Swap b, c -> [b,c,a]
    Step 3. Swap a, a -> [b,c,a]

What is the probability that we do exactly these steps? At each step, we have 3 choices, so (1/3) * (1/3) * (1/3) = 1/27. What is the probability that we end up with [b,c,a] ? You might think 1/27 as well, but that is not quite true – it is possible, that we choose different steps, but end up with the same result. For example, we can do [a,b,c]->[b,a,c]->[b,c,a]->[b,c,a]. But the probability will always be a multiple of 1/27 – it is just 1/27 times the number of possible paths that leads to [b,c,a].

Now, what should the probability be? There are exactly 6 ways to shuffle [a,b,c] (this is the number of permutations, 3! = 3 * 2 * 1 = 6). So we want to get [b,c,a] with a probability of 1/6. But 1/6 is not a multiple of 1/27 ! (You can see that by looking at the equation 1/6 = x/27, which is the same as x = 27 / 6 = 4.5 .)

The same argument works for any length n > 2, as n*n is not divisible by n-1, but n! is.

Info why it doesn't work: the smallest array for which it fails has 3 elements. When you start with a sorted array, iterate through each element and move it to one of the 3 positions with equal probability, there are 3³ = 27 possible move sequences, each with probability 1/27, but only 3! = 6 possible outcomes (permutations of the array). Because 6 doesn't divide 27, there must be some outcomes that are generated by more move sequences than others and hence occur more often.

This feels like it should work from a clear induction argument.

Base case: n=1. Obvious.

Inductive step: n>1. The nth element swaps to itself w/ prob 1/n, and to any other element w/ prob 1/n. By induction the other elements have been uniformly shuffled. Any of those elements is swapped to the nth place w/ prob 1/n.

I don't think you can apply this proof to the described algorithm.

This proves that

    for i in range(min_key,max_key):
        swap(arr, i, choice(i, max_key))

works as a shuffle, by growing a random sub-array.*

The first algorithm was

    for i in range(min_key,max_key):
        swap(arr, i, choice(min_key, max_key))

which has different biases.

* I am not actually sure that this actually works.

Ah, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.

Your first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)

If your n-1 elements are uniformly shuffled, swapping with them would undo that. So to preserve the uniformity invariant, you have not to touch elements that were already shuffled, which leads you to Fisher–Yates.

True shuffling is pretty easy to achieve, most programming language already have array.shuffle() methods.

Reply on news.ycombinator.com