Fisher–Yates の方法

互いに異なる $n \ge 1$ 個の元が入った配列 $a[0], \ldots, a[n-1]$ に対して、$i = n-1, n-2, \ldots, 1$ の順に「$\{0, 1, \ldots, i\}$ 上の一様分布に従う $J_i$ を（それまでの $J$ と独立に）選び、$a[i]$ と $a[J_i]$ を交換する」操作を行う。

1. $1 \le k \le n - 1$ とする。最初の $k$ 回の操作（$i = n-1, \ldots, n-k$）の後、互いに異なる任意の元 $e_1, \ldots, e_k$ について $$\mathbb{P}\bigl(a[n-1] = e_1,\ a[n-2] = e_2,\ \ldots,\ a[n-k] = e_k\bigr) = \frac{1}{n(n-1)\cdots(n-k+1)}$$ である。したがって、末尾の $k$ 個の位置にある元の集合は、$\binom nk$ 通りの $k$ 元部分集合の上で一様に分布する。
2. すべての操作の後の配列は、$n!$ 通りの並べ方の上で一様に分布する。
3. 「$i = 0, 1, \ldots, n-1$ の順に、$\{0, \ldots, n-1\}$ 上の一様分布に従う $J_i$ を独立に選び、$a[i]$ と $a[J_i]$ を交換する」方法では、$n \ge 3$ のとき配列は一様に分布しない。