Array Shuffle

Array shuffle rearranges elements into a random order such that every permutation is equally likely.

You use it when unbiased randomization is required, such as sampling, randomized algorithms, or testing.

Problem

Given an array $A$ of length $n$, produce a permutation where each of the $n!$ possible orderings occurs with equal probability.

Algorithm

Use the Fisher–Yates shuffle. Iterate from the end and swap each position with a random earlier position.

shuffle(A):
    n = length(A)

    for i from n - 1 down to 1:
        j = random integer in [0, i]
        swap A[i], A[j]

Example

Let

$$ A = [8, 3, 5, 1] $$

Suppose random choices are:

• $i = 3$, choose $j = 1$ → swap positions $3$ and $1$
• $i = 2$, choose $j = 0$ → swap positions $2$ and $0$
• $i = 1$, choose $j = 1$ → no change

step	i	j	array
1	3	1	[8, 1, 5, 3]
2	2	0	[5, 1, 8, 3]
3	1	1	[5, 1, 8, 3]

Result:

$$ [5, 1, 8, 3] $$

Correctness

At step $i$, the algorithm selects a random element from indices $[0, i]$ and places it at position $i$. Each element has equal probability of being chosen at each step.

By induction:

• the last position is uniformly random
• the remaining positions are shuffled independently in the same way

Thus every permutation occurs with probability:

$$ \frac{1}{n!} $$

Complexity

operation	time
shuffle	$O(n)$

Space usage:

$$ O(1) $$

When to Use

Array shuffle is appropriate when:

• unbiased random permutation is required
• randomized algorithms depend on uniform input
• sampling without replacement is needed

It is less suitable when:

• reproducibility without a fixed seed is required
• cryptographic randomness is needed, in which case a secure RNG must be used

Implementation

import random

def shuffle(a):
    n = len(a)
    for i in range(n - 1, 0, -1):
        j = random.randint(0, i)
        a[i], a[j] = a[j], a[i]

import "math/rand"

func Shuffle[T any](a []T) {
    n := len(a)
    for i := n - 1; i > 0; i-- {
        j := rand.Intn(i + 1)
        a[i], a[j] = a[j], a[i]
    }
}