4 ms·
I know Knuth wrote it that way, but there's no good reason why the iteration should be downwards. That is, you could write: for i in range(1, len(x)) and yo
by jwilk 4y ago
I know Knuth wrote it that way, but there's no good reason why the iteration should be downwards. That is, you could write:
for i in range(1, len(x))
and you would still get an unbiased shuffle algorithm.
The upwards iteration has a few advantages:
• You can start shuffling before you know how big the input is.
• Algorithm R for reservior sampling can be seen a specialized version of shuffling, in which you skip the work that wouldn't affect the first k items, or would only affect their order.
- chkas 4y agoIf you want to do it the other way around, you have to start at 0: for i in range(len(x) - 1): r = randrange(i, len(x)) x[i], x[r] = x[r], x[i]
- jwilk 4y agoThat probably works too, but it's even more awkard than the Knuth's one, and doesn't have the nice properties I mentioned. I meant just: for i in range(1, len(x)): r = randrange(i + 1) x[i], x[r] = x[r], x[i]