Home » programming » Everyday I’m Shufflin

Everyday I’m Shufflin

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: