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; } } }

Last updated 04 Apr 2004 16:19. Copyright © 2004 Ben Pfaff.

May be freely redistributed, but copyright notice must be retained.