The Knuth Shuffle Algorithm

Problem Introduction

Let's first consider a question: Given an array of size 100 with elements arranged from 1 to 100 in order, how can we randomly select one number from it?

The simplest way is to use the system method Math.random() * 100, which will give a random number between 0 and 99, and then use it as an index to select the corresponding element in the array.

Next, consider another question: Given the same array, how can we randomly select 50 numbers?

The numbers must not repeat. If you simply select 50 numbers randomly, the issue of duplicate numbers may arise.

One possible modification is to store each randomly generated number in an array, and for each subsequent random selection, check if the number is already in the array. If it is, continue to randomly select until 50 unique numbers are chosen.

This method works but has a problem. When the number of selections approaches the size of the array, the probability of repeated numbers increases significantly. For example, if you need to select 99 numbers from an array of size 100, following the above approach, as the number of selected numbers increases, the probability of selecting a duplicate number also increases, making the process less efficient.

In this case, we can consider another approach: shuffle the array first, and then directly select the first 50 numbers.

This approach works, but the key is to ensure that the "shuffle" is truly random. For example, a deck of cards has 54 cards, and there are $54!$ possible arrangements. A shuffle should be able to generate any of these $54!$ arrangements with equal probability.

Shuffle Algorithm

The Fisher-Yates shuffle algorithm was proposed by Ronald Fisher and Frank Yates in 1938 and later adapted for computer programming by Richard Durstenfeld in 1964.

The algorithm is very simple: starting from the last element of the array, swap it with any one of the previous elements (including itself). Then, swap the second-to-last element with one of the remaining elements, and so on.

This process ensures that every element has an equal probability of appearing in any position.

Program Implementation

function knuthShuffle<T = any>(array: T[]): T[] {
  const result = array.slice();
  for (let i = result.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

const arr = [1, 2, 3, 4, 5];
console.log(knuthShuffle(arr));

Proof

The Knuth Shuffle algorithm (also known as the Fisher-Yates Shuffle) can generate all possible permutations with equal probability. To prove that the algorithm is effective in shuffling any sequence, the key is to ensure that each permutation appears with equal probability. Below is the mathematical proof.

For a sequence of $n$ elements, starting from the last element, randomly select one of the previous elements (including the current one) to swap. The steps are as follows:

1. For the $i$-th element (starting from $i = n$ down to $i = 2$), randomly select an index $j$ from the range [0, $i-1$] and swap element $a[i]$ with element $a[j]$.
2. Finally, all elements in the sequence are swapped once.

Objective

We need to prove that this algorithm generates all possible permutations with equal probability. For a sequence of length $n$, there should be $n!$ different permutations, and each permutation should have a probability of $\frac{1}{n!}$.

Analysis

1. Total number of permutations
   For an array of length $n$, the total number of possible permutations is $n!$. That is, for $n$ elements, the number of unique permutations is:

   $$P(n) = n! = n \times (n-1) \times \cdots \times 2 \times 1$$

2. Random selection process in the algorithm
   In the $i$-th step, the Knuth Shuffle algorithm randomly selects an index between 0 and $i$ to swap. This selection is uniform, so the probability of selecting any index is $\frac{1}{i+1}$.

   • Step 1: Choose one element out of $n$, with probability $\frac{1}{n}$.
   • Step 2: Choose one of the remaining $n-1$ elements, with probability $\frac{1}{n-1}$.
   • And so on, until no elements remain to swap.

3. Probability of generating a specific permutation
   To prove that Knuth Shuffle generates all permutations with equal probability, we need to show that the probability of generating any specific permutation is $\frac{1}{n!}$.

   The probability of any element being swapped into a certain position is independent for each step:

   • The $n$-th element can be swapped with any of the $n$ elements, with probability $\frac{1}{n}$.
   • The $(n-1)$-th element can be swapped with any of the remaining $n-1$ elements, with probability $\frac{1}{n-1}$.
   • And so on.

   Therefore, the probability of generating any particular permutation is:

   $$\frac{1}{n} \times \frac{1}{n-1} \times \cdots \times \frac{1}{1} = \frac{1}{n!}$$

4. Equal probability for all permutations
   Since the probability of generating each permutation is $\frac{1}{n!}$ and there are $n!$ distinct permutations, the Knuth Shuffle generates all possible permutations with equal probability.

In conclusion, the Knuth Shuffle algorithm ensures that every element is swapped with equal probability in each step, and the resulting permutations are uniformly distributed across all $n!$ possible permutations. Therefore, the Knuth Shuffle is an effective algorithm for shuffling any sequence in a uniformly random manner.