4 ms·
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
by 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 agoI 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 agoAh, I see what you mean. I assumed the first algorithm was what they meant; I have no comment on the second algorithm.
- mananaysiempre 4y agoYour first one is one of the versions of the standard Fisher–Yates shuffle, so it does work :)
- LudwigNagasena 4y agoIf 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.