Sunday, March 07, 2010

An implementation of Fisher-Yates Algorithm

The recent news of Microsoft's ballot screen certainly piqued my interest. It's not really the browser ballot that interests me rather it's the fact that there's an issue with the randomness of the browser list. Internet Explorer seems to display much more frequently on one side of the screen when the ballot is done on Internet Explorer and Firefox browsers.

More specifically, there's mention of a simple yet effective shuffling algorithm called the Fisher-Yates algorithm that would have avoided the 'problem' had Microsoft implemented it instead of whatever method they did.

I'm always interested in simple yet powerful algorithms, so after reading up on how it's supposed to work here's my implementation in Python:

def shuffle(items):
    for i in range(len(items)):
        j = randrange(len(items))
        items[i], items[j] = items[j], items[i]


There's other implementations out there which I'm sure can be easily Googled. The simplicity of the algorithm really makes you wonder what Microsoft was thinking when they did it their way. Do they want to 'innovate' that badly?