|
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. |