Shuffle Algorithms

Ever wondered why when you select the Shuffle option in your Ipod, MP3 or whatever gadget that you are using to play your music, there is something peculiar with the randomness of teh choice of songs. Somehow some tracks just get repeated too often, especially when your collection is limited alot. Well, I recently took time to explore what goes on behind the 'scenes' and discovered something puzzling. There is a problem with the shuffling, that is, it is random. I know this sounds like am kidding but I am not, be assured. A simple random function implementation in Python for example generates the following:

AACBBCBACABBCCACCCCABBACBACABABB 

And I am pretty sure implementation in other languages will generate something of similar manner. Now, it does not take much effort to see that the randomness of the above output is not what we desire. Assuming that A, B, and C are tracks, one can easily notice the biasness to C in the middle of the shuffle. Also there are very few instances of B. This is not what is intuitively believed to be shuffling. Because we want shuffle to give equal chance to every track in the playlist and do so in a random manner, but what do we get; a 'randomness that is random'. To explain the intuitive understanding of shuffle, this is what we expect with shuffle 'on'.

ABCBCABACBACBCABCACBABCACBACBCAB

But, this is where the problem comes, how do we develop a shuffle algorithm that is efficient enough to generate something like the one shown above from the playlist. I will discuss a possible algorithm that solves this problem next time. Till then, have fun pondering over the problem.