How to shuffle a deck of cards in a fast efficient way? Or, given an array of length n (e.g. 10000) and natural numbers from 1 to n, how to reorder the data series to be as random as possible (random permutation)? This is a classic computer science question, and it makes a good technical interview question.
Knuth shuffle algorithm is an elegant and fast algorithm to do shuffling. Let X1, X2…. XN be the set of N numbers to be shuffled.
1. Set j to N
2. Generate a random number R. (uniformly distributed between 0 and 1)
3. Set k to (jR+1). k is now a random integer, between 1 and j.
4. Exchange Xk and Xj
5. Decrease j by 1.
6. If j > 1, return to step 2.
void KnuthShuffle(int* pArr)
{
int rand;
for(int i=N-1; i>=0; i--)
{
rand = GenRand(0,i);
swap (pArr[i], pArr[rand]);
}
}
Note: The algorithm is copied from here which has more detailed information.
