Fisher–Yates Shuffle: Uniform Permutations and Common JavaScript Mistakes

For n distinguishable items, there are n! possible permutations: 6 for three items, 120 for five, and 3,628,800 for ten. A deck of 52 distinct cards has approximately 8.07 × 10⁶⁷ permutations. Even when two items have the same value, we can distinguish them by their original positions for this analysis.

A uniform shuffle gives every permutation probability 1/n!. Equal position frequencies alone are insufficient. A procedure that returns only ABC, BCA, and CAB with equal probabilities places each item equally often in every position, yet never generates half of the six possible permutations.

Fisher–Yates meets the stronger condition when the swap index at each step is uniform even after conditioning on earlier choices. The random source and the conversion into a bounded integer are part of that requirement.

Ronald A. Fisher and Frank Yates first published Statistical Tables for Biological, Agricultural and Medical Research in 1938. The university-held sixth edition listed in the references is dated 1963; it is not the 1938 edition.

The paper-and-pencil approach selects one of the remaining items uniformly, removes it, and writes it into a new sequence. This is useful for randomizing experimental orders and assignments.

1. List the original items.
2. Choose one remaining item uniformly.
3. Append it to the output and remove it from the list.
4. Repeat until no items remain.

Whether the choices come from a random-number table or software, converting them into an allowed range must not favor particular items. The next step is to make this process efficient on an array.

Richard Durstenfeld’s 1964 paper, Algorithm 235: Random Permutation, describes swapping a random item into the last unfilled position. Repeatedly removing an item and closing a gap in an array can take O(n²) time. Swapping avoids that repeated shifting.

for i = n-1 down to 1:
  j = uniform integer in [0, i]
  swap(arr[i], arr[j])

Choose j from 0 through i, including both endpoints, then fix position i. Swapping an item with itself is an essential possibility. With constant-time swaps and random draws, the in-place algorithm takes O(n) time and O(1) auxiliary space. In-place does not mean that it uses literally no additional memory.

Knuth discusses the method as Algorithm P in Volume 2 of The Art of Computer Programming, and it is also known as the Knuth shuffle. This naming does not indicate certification by a standards body.

Start with ABC. The first swap has three possible partners and the next has two. With uniform choices, each of these six paths has probability 1/6.

For any desired final permutation, the item required in the last position determines a unique first swap. The next required item determines a unique second swap, and so on. This gives a one-to-one correspondence between choice paths and permutations. Each path has probability 1/n × 1/(n−1) × … × 1/2 = 1/n!. Counting n! paths without establishing that correspondence would not be enough.

At every step, every integer in 0..i must remain equally likely conditional on the earlier choices. Empty and one-item arrays each have just one possible ordering and need no swaps.

Do not use this as a uniform shuffle:

arr.sort(() => Math.random() - 0.5);

A sort comparator must produce consistent results for the same pair and satisfy properties such as reflexivity and transitivity. Random comparisons break that contract. ECMAScript makes the ordering implementation-defined when the comparator is inconsistent. It does not promise a particular sorting algorithm or an O(n log n) comparison count.

The observed bias depends on the engine, version, and input. It need not have the same shape in every case. The absence of a uniformity guarantee is already enough to rule it out for a fair draw. Also remember that sort modifies the original array.

This loop has a different problem:

for (let i = 0; i < n; i++) {
  const j = Math.floor(Math.random() * n);
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

For n = 3, even ideal uniform integer choices produce 3³ = 27 equally likely paths. They cannot be divided equally among six permutations. Exhaustive enumeration gives each permutation either four or five paths. This counterexample does not imply a bias in trivial cases such as an empty or one-item array.

In the descending Fisher–Yates loop, i runs from n−1 down to 1 and j is in 0..i. An ascending variant instead runs i from 0 to n−2 and chooses j in i..n−1. Changing only the loop direction while retaining the old range is not equivalent.

Excluding i from the descending range, so that j is chosen from 0..i−1, gives a Sattolo-style single-cycle generator. That has a different purpose: it does not generate all permutations and cannot replace a shuffle that allows an item to remain in its original position.

If r is a uniform unsigned 32-bit integer, r % n is biased unless n divides 2³². Write 2³² = qn + k. Remainders 0..k−1 each have q+1 preimages, while every other remainder has q.

For n = 7, q = 613,566,756 and k = 4. The absolute difference between the two probabilities is 1/2³². There is no bias for n = 2³¹, but at n = 2³¹+1 some values are twice as likely as others. Bias does not increase monotonically with n.

Rejection sampling discards values at or above limit = floor(2³²/n) × n, then applies % n. The accepted range contains a whole number of complete sets of remainders. For n = 7, discard the last four 32-bit values.

The following browser example accepts a normal dense array, makes a shallow copy, and leaves the original array unchanged. Objects stored as elements are not cloned. An unavailable or failing Crypto API causes an error; the example does not fall back to Math.random.

function unbiasedRandomInt(n) {
  const range = 2 ** 32;
  if (!Number.isInteger(n) || n < 1 || n > range) {
    throw new RangeError("Expected an integer from 1 to 2^32");
  }
  const source = globalThis.crypto;
  if (!source || typeof source.getRandomValues !== "function") {
    throw new Error("Web Crypto is unavailable");
  }
  const limit = Math.floor(range / n) * n;
  const value = new Uint32Array(1);
  for (let attempt = 0; attempt < 128; attempt++) {
    source.getRandomValues(value);
    if (value[0] < limit) return value[0] % n;
  }
  throw new Error("Random sampling did not complete");
}

function shuffledCopy(items) {
  if (!Array.isArray(items)) throw new TypeError("Expected an array");
  const result = [...items];
  for (let i = result.length - 1; i > 0; i--) {
    const j = unbiasedRandomInt(i + 1);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

console.log(shuffledCopy(["A", "B", "C"]));

The swaps take O(n) time and the copy takes O(n) space. Each bounded integer draw stops with an error after 128 unsuccessful attempts. Under an independent, uniform 32-bit model, each attempt accepts more than half the possible values, so 128 consecutive rejections have probability below 2⁻¹²⁸. This cap prevents an endless retry loop; it does not limit the time spent inside Web Crypto itself. A partially shuffled result is never returned after failure.

Math.random returns an approximately uniform value from 0 inclusive to 1 exclusive, but ECMAScript leaves its method and discrete output set implementation-defined. It does not guarantee cryptographic unpredictability or exact uniformity after floating-point range conversion. Web Crypto fills integer typed arrays; this example selects Uint32Array to obtain 32-bit values. The API is not limited to that element width. In Node.js, crypto.randomInt(0, i + 1) offers bounded integer selection that avoids modulo bias.

An API contract is different from a particular version’s internal algorithm. These APIs support shuffling, but their default random sources are not necessarily appropriate for cryptography.

A proposed feature is not an available standard API. Choose separately for uniformity, unpredictability, and reproducibility from a seed. A finite-period pseudorandom generator also cannot reach every permutation once the array is sufficiently large.

The implementations serve different purposes. The following table describes the Japanese tools.

A random source, a bounded-integer mapping, and a permutation algorithm each need their own checks. The draw tool maps 32-bit values to swap positions and applies Fisher–Yates. The other tools select faces, candidates, or characters without shuffling a whole array. An algorithm’s name does not establish independently audited fairness or the safety of every application that uses its output.

Generating random values and using them to reorder a sequence are separate tasks. For the related question of password strength, see the published password entropy and NIST guide.

• Uniform permutations require more than equal frequencies for each item’s position.
• In the descending loop, choose uniformly from 0..i, conditional on earlier choices.
• A random comparator, full-array swap range, or exclusion of i is not a substitute for uniform permutation generation.
• Use rejection sampling when mapping a uniform integer source to a bounded range, and handle invalid bounds and failures.
• Uniformity and unpredictability are distinct. The algorithm alone does not satisfy the auditing requirements of an official draw.

Cards drawn without replacement are not independent trials. The probability that two cards drawn from a 52-card deck are both aces is 4/52 × 3/51 = 1/221. The first draw changes what remains.

By contrast, the number of successes in independent trials with a constant success probability p follows a binomial distribution. At p = 0.03, the chance of at least one success in 33 independent trials is 1−0.97³³ ≈ 63.4%. A guarantee threshold or changing success probability requires a different model.

NanToo’s Japanese probability tools cover independent draws with separate guarantee conditions, and sums of independent dice through convolution. Those models must not be applied unchanged to drawing cards without replacement.