I don’t remember the link but there was a gambling site a while back that published their randomization algorithm in an attempt to show how fair they were. It went as follows:
for each element in list
pick position in the entire list to put this element in the list.
swap elements with the current and picked position
The problem with that is that items at the front of the list will be moved more times on average than items at the end of this list. This is because items which are moved earlier (items at the front of the list) have more chance to be moved past the current index into the list, thus being picked to be moved again. This distorts the randomization curve such that items at the end of the list are more likely to stay there.
As a result, they got hacked.
Here’s the proper way to randomly sort a list in place:
void SystemAddressList::RandomizeOrder(void)
{
unsigned index, size, randIndex;
PlayerID temp;
size = systemList.Size();
for (index=0; index < size; index++)
{
randIndex=index + (randomMT() % (size-index));
if (randIndex!=index)
{
temp=systemList[index];
systemList[index]=systemList[randIndex];
systemList[randIndex]=temp;
}
}
}
2 replies on “How to randomize a list in order”
Sorry, but I think the algorithm you posted is the same you described up there, isn’t it?
“for each element in list
pick position in the entire list to put this element in the list.
swap elements with the current and picked position”
Except, that it doesn’t pick fromt he entire list everytime. It picks from the current index to the end of the list.
The algorithm I first described is the wrong one and it picks from the entire list every time. The code I posted uses the correct algorithm and only picks from the current index to the end of the list.