Fisher-Yates shuffle

Background

The Fisher–Yates shuffle produces a uniformly random permutation of a sequence in $O(n)$ time and in place. Walking from the last index down to the first, it swaps each element with a uniformly chosen element at or before it. Every one of the $n!$ permutations is equally likely — which naive "swap each with a random index in $[0,n)$" approaches fail to guarantee.

Problem statement

Implement fisher_yates_shuffle(arr, seed=None) returning a shuffled copy of arr:

$$\text{for } i = n-1 \text{ down to } 1:\quad j \sim \text{Uniform}\{0,\dots,i\},\quad \text{swap } a_i \leftrightarrow a_j$$

Use np.random.default_rng(seed) for the random indices.

Input

• arr — a sequence (list or np.ndarray) of length n.
• seed — int or None, RNG seed for reproducibility.

Output

An np.ndarray of length n: a permutation of arr. The input must not be mutated.

Examples

Example 1

Input:  arr = [1, 2, 3, 4], seed = 0
Output: a length-4 permutation of {1, 2, 3, 4} (e.g. [3, 1, 4, 2]); same seed always gives the same result

Explanation: the algorithm swaps each position with a uniformly chosen earlier-or-equal position, yielding a uniformly random reordering. Fixing the seed makes the output deterministic.

Constraints

• The chosen index $j$ at step $i$ must be drawn from $\{0,\dots,i\}$ inclusive (so an element can stay in place).
• Operate on a copy — do not modify the caller's array.
• The result is always a permutation (same multiset of elements).

Notes

• Drawing $j$ from $[0, i]$ (not $[0, n)$) is exactly what makes the shuffle uniform; the common bug of using $[0, n)$ biases the distribution.
• It is the algorithm behind np.random.shuffle and random.shuffle.