Shuffle

Uniformly random permutation of sample $\mathbf{x}$ using generator $r$.

• Algorithm — Fisher-Yates (Knuth shuffle), see Shuffle
• Complexity — $O(n)$ time, $O(n)$ space (returns new array)
• Output — new array (does not modify input)

Properties

• Uniformity each of $n!$ permutations has equal probability
• Determinism same generator state produces same permutation

Example

• Rng("demo-shuffle").Shuffle([1, 2, 3, 4, 5]) — shuffled copy
• r.Shuffle(x) preserves multiset (same elements, different order)

Implementation names

$\operatorname{Shuffle}$ produces a random reordering of data. This is essential for permutation tests and useful for eliminating any bias from the original ordering. Every possible arrangement has exactly equal probability, which is required for valid statistical inference. The function returns a new shuffled array and leaves the original data unchanged. For reproducible results, pass a seeded generator: Shuffle(data, Rng("experiment-1")) will always produce the same permutation.

Algorithm

The $\operatorname{Shuffle}$ function uses the Fisher-Yates algorithm (see Fisher & Yates 1938, Knuth 1997), also known as the Knuth shuffle, with the Rng generator for random decisions:

for i from n-1 down to 1:
   j = uniform_int(0, i+1)
   swap(array[i], array[j])

This produces a uniformly random permutation in $O(n)$ time with $O(n)$ additional space (the input is copied). The algorithm is unbiased: each of the $n!$ permutations has equal probability.

Tests

The $\operatorname{Shuffle}$ test suite contains 12 test cases validating random permutation. Given a seed and input array $\mathbf{x}$, $\operatorname{Shuffle}$ returns a permutation of $\mathbf{x}$ using the FisherYates algorithm. All tests verify reproducibility: the same seed and input must produce the same permutation across all language implementations.

Seed variation ($n = 5$, $\mathbf{x} = (1, 2, 3, 4, 5)$) 3 tests with different seeds:

• seed-0-n5-basic: seed $= 0$
• seed-123-n5-basic: seed $= 123$
• seed-999-n5-basic: seed $= 999$

These tests validate that different seeds produce different permutations of the same input.

Fixed seed (seed $= 1729$) 9 tests exploring different input sizes and content:

• seed-1729-n1-single: $\mathbf{x} = (1)$ (trivial case, single element)
• seed-1729-n2-basic: $\mathbf{x} = (1, 2)$ (minimum non-trivial case)
• seed-1729-n5-basic: $\mathbf{x} = (1, 2, 3, 4, 5)$ (standard case)
• seed-1729-n5-zeros: $\mathbf{x} = (0, 0, 0, 0, 0)$ (all identical, permutation preserves content)
• seed-1729-n6-neg: $\mathbf{x} = (-5, -3, -1, 1, 3, 5)$ (negative and positive values)
• seed-1729-n10-seq: $\mathbf{x} = (0, 1, \ldots, 9)$ (10-element sequential)
• seed-1729-n20-seq: $\mathbf{x} = (0, 1, \ldots, 19)$ (20-element sequential)
• seed-1729-n100-seq: $\mathbf{x} = (0, 1, \ldots, 99)$ (large array)
• seed-123-n10-seq: seed $= 123$, $\mathbf{x} = (0, 1, \ldots, 9)$ (different seed, same size as n10-seq)

The progression from $n = 1$ to $n = 100$ validates that the FisherYates implementation scales correctly. The zero-valued and negative-valued tests verify that shuffling operates on positions, not values.

References