Random shuffling of a ordered set of numbers would end up in a different order. Mathematically, result is a different combination. Also, Random shuffle needs the algorithm output all possible combinations with equal probability. Say 1, 2, 3 is our input, then probability of getting the result 3, 2, 1 should be tantamount of getting 2, 3, 1. So, getting a specific output for the given input of cardinality 'n' should have the probability 1 / (n!).
The Fisher-Yates algorithm for the above problem is very elegant. Idea is to select the first number out of "n" possibilities and next out of "n-1" possibilities and so on. So, we will get an output which has the probability of occurring, 1 / n!.
Please find the code-snippet, below for the same.
for( int i = Length - 1; i > 0; i--)
{
int currentRandomIndex = GetNextRandomNumber(0, i);
Swap( inArray[i], inArray[currentRandomIndex];
}
If you write the algorithm for this on your own, there are possibilities to make subtle mistakes like the one in this link, http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html
Another interesting variant is collecting "n" random samples out of huge set of cardinality "N". I have discussed the same in the blog,
No comments:
Post a Comment