consider these two shuffling algorithms written in pseudo code, operating on a vector v with n elements:
Code:
for i = 1 to n, step 1
j = random integer in the interval [i, n]
if i $\displaystyle \neq$ j, swap elements in v on place i and place j
end
and
Code:
for i = 1 to n, step 1
j = random integer in the interval [1, n]
if i $\displaystyle \neq$ j, swap elements in v on place i and place j
end
To me it's obvious that the first algorithm will guarantee that all the n! different permutations of shuffeled vectors will have equally big chance to take place. But what about the second algorithm? Although I suspect that the same thing applies to this, I am not sure about it. Can someone please help me to prove whether this is true or not, if all n! permutations of the shuffeled vectors have equally big chance to take place or not, using the second algorithm? The only difference between the two algorithms is that the first one uses random numbers generated in the interval [i, n], while the second one uses random numbers generated in [1, n]. Oh, and about the generated numbers, all integers in the given interval has equaly big chance to be generated each time.