4 ms·
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_ke
by 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 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 :)