import random
list = [0,1,2,3,4,5,6,7,8,9]
length = len(list)
for i in range(1,length):
j = length - i
k = random.randrange(j+1)
list[j], list[k] = list[k], list[j]
print(list)
[3, 9, 6, 4, 7, 8, 5, 1, 0, 2]
The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.
That code doesn't work as written (there is an off-by-one error in the first iteration of the loop). But the intended algorithm (starting at the end of the list, swap each element with a random predecessor) doesn't produce a uniform distribution anyway; for instance it will never produce an output where the last element is unchanged.
I had an error which I believe I have now fixed. The intended algorithm is "starting at the end of the list, swap each element with a random predecessor or possibly with itself".
Wouldn't this have a bias to how the initial input sequence is?
EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.
