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

Last updated 04 Apr 2004 16:19. Copyright © 2004 Ben Pfaff.
May be freely redistributed, but copyright notice must be retained.