# How to shuffle an array

Nov. 24, 2021

Suppose we have an array of N elements and we need to reorder it randomly. That is a common scenario in machine learning problems when we want to extract a random sample of observations from a dataset. Another scenario is when we want to divide the dataset into random blocks, for example train and test subsets. A solution is to shuffle the dataset and take n sequential elements for each block.

To shuffle a dataset, we can start with an array of N sequential numbers that represents the order of the dataset observations. We shuffle that array and next, we use it as indices to retrieve the observations. A pseudocode solution is shown below.

```
Input:
D : dataset
N : number of observations
Output:
D' : suffled dataset
x := 1..N
x' := shuffle(x)
D' := D[x'[1]], D[x'[2]], ..., D[x'[N]]
return D'
```

Therefore, we need a shuffle() function to efficiently shuffle the array of indices. For that, we can use the Fisher-Yates algorithm (1948) that runs in O(n) time. It uses a random number r between 1 and N-1 to swap the element at position N with the element at position r. As a result, the element at position N is already shuffled. The procedure is recursively repeated for the N-1 remaining elements.

```
Function: shuffle
Input:
N : array size
Output:
x : shuffled array
x := 1..N
i := N
while i > 1:
r := random(i - 1)
v := x[i]
x[i] := x[r]
x[r] := v
i := i - 1
return x
```

The implementation in C of the shuffle() function is presented below. A random number generator from the GNU Scientific Library (GSL) has been used. Indices have been adjusted because in C arrays start at 0 instead of 1.

```
#include <gsl/gsl_rng.h>
int *shuffle(int N, int seed) {
int i;
int r, v;
int *x = malloc(sizeof(int) * size);
/* Random number generator allocation */
gsl_rng *rndgen = gsl_rng_alloc(gsl_rng_taus);
gsl_rng_set(rndgen, seed);
/* Vector initialization */
for (i = 0; i < size; i++)
x[i] = i;
/* Shuffling algorithm */
for (i = size - 1; i > 0; i--) {
r = gsl_rng_get(rndgen) % i;
v = x[r];
x[r] = x[i];
x[i] = v;
}
/* Cleanning */
gsl_rng_free(rndgen);
return x;
}
```

References:

- Fisher, R. & Yates, F. (1948). Statistical tables for biological, agricultural, and medical research (3rd. Ed.). London: Oliver & Boyd. pp. 26-27.
- Fisher–Yates shuffle. In Wikipedia. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle