I’m sure you have all heard about the problems with certain mp3 players and their ‘random’ play lists. Some people think they repeat some songs more than others. Well here a way to get a truly random shuffle of the list in constant time. That means it takes the same amount of time no matter how big the list is.
This class takes takes an Array of items (data) and divides it into two sections. The first section is the already randomized items, the other is the items that haven’t been shuffled yet. When you request the next item, it picks a random item from the remaining set and swaps it onto the end of the shuffled set. When the non-shuffled set is empty, it starts from the beginning of the array again. At this point the whole array would have been shuffled already so no more swapping will be needed.
Here is the entire class in C#
class Shuffle
{
Random r = new Random();
Object[] data;
int split; // where the split is in the array
bool shuffled = false; // has the entire array been shuffled
public Shuffle(Object[] q)
{
split = 0;
data = q;
}
public Object Next()
{
if (split == data.Length)
{
split = 0;
shuffled = true;
}
if (!shuffled)
{
// find the next one
int idx = r.Next(data.Length – split);
// swap the positions
Object tmp = data[split];
data[split] = data[idx];
data[idx] = tmp;
}
return data[split++];
}
}This class shuffles the list in constant time. It only shuffles when a new item is requested from the list, and only shuffles that one item. This is many many times faster than shuffling all the items at once.
Enjoy.