Tonight, we had a discussion with Marco about whether the following simple algorithm would work well enough in order to shuffle an array. Given are a random number generator and the array that we want to shuffle. Here is the code of the algorithm in Python.
(Implementation note: we assume that -1 is an invalid value for the input vector.)
import random def shuffle(l): shuffled_l = [-1] * len(l) for i in range(len(l)): ri = random.randint(0, len(l) - 1) while shuffled_l[ri] != -1: ri = (ri + 1) % len(l) shuffled_l[ri] = i return shuffled_l
In order to test it, we shuffled many times the numbers from 0 up to 100. Then, we took the sum of the resulting vectors. In every position, we should see about the same number if our shuffling works well.
def vector_add(v1, v2): res =  for a, b in zip(v1, v2): res.append(a + b) return res def main(): N = 100000 l = list(range(100)) v1 = shuffle(l) for i in range(N): v2 = shuffle(l) v1 = vector_add(v1, v2) for i in range(len(v1)): v1[i] /= N print(v1) if __name__ == "__main__": main()
Of course, that does not consist of a proof that the algorithm works but it looks good enough to me (but it is late). There are other approaches like Knuth shuffle which are even simpler and it is proven that they work correctly. Moreover, Python also already offers a shuffle method.