4 ms·

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 di

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?

charlieyu1 4y ago
True shuffling is pretty easy to achieve, most programming language already have array.shuffle() methods.
senkora 4y ago
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.
- afiori 4y ago
  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.
  - senkora 4y ago
    Ah, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.
  - mananaysiempre 4y ago
    Your first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)
- LudwigNagasena 4y ago
  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.
yorwba 4y ago
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.
suyjuris 4y ago
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.

charlieyu1 4y ago

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

senkora 4y ago

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.

afiori 4y ago
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.
- senkora 4y ago
  Ah, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.
- mananaysiempre 4y ago
  Your first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)
LudwigNagasena 4y ago
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.

yorwba 4y ago

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.

suyjuris 4y ago

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.