How can I shuffle the contents of an array?

The function below is a reasonable way to shuffle an array into pseudo-random order in C. The quality of the shuffle depends on the quality of implementation of the rand() function. Many implementations of rand() have predictable lower bits, so the function instead extracts randomness from the upper bits of rand()'s return value, as described in C FAQ 13.16.

The shuffle's quality is also influenced by UINT_MAX, the number of possible seed values passed to srand(). Many implementations of the standard C random functions only have UINT_MAX + 1 possible internal states, so that there will only be UINT_MAX + 1 shuffles total for a given n.

An array of n unique elements can be shuffled n! (n factorial) different ways. For a 52-card deck, that's over 8e67 ways, whereas UINT_MAX is permitted to be as small as 65,535, meaning that only about 1 in 1e63 of the potential shuffles will actually ever appear. The best solution is probably to use a better pseudo-random number generator, one that has at least 226 bits of internal state.

For the true story of how a badly seeded random number generator led to predictable shuffles, see Viega and McGraw, Building Secure Software, pp. 238–241, section “How to Cheat in On-line Gambling.”

#include <stdlib.h>

/* Arrange the N elements of ARRAY in random order.
   Only effective if N is much smaller than RAND_MAX;
   if this may not be the case, use a better random
   number generator. */
void shuffle(int *array, size_t n)
{
    if (n > 1) {
        size_t i;
	for (i = 0; i < n - 1; i++) {
	  size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
	  int t = array[j];
	  array[j] = array[i];
	  array[i] = t;
	}
    }
}