# Array Shuffle

# 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.

```id="array-shuffle"
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

```python id="array-shuffle-python"
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]
```

```go id="array-shuffle-go"
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]
    }
}
```