Perfect Shuffle: The Strange Fractals Hidden in a Simple Algorithm

Source: Dev.to

Introduction

I have always been fascinated by elementary algorithms that create complex patterns. One such algorithm is the Perfect Shuffle (known among card magicians as the Faro Shuffle). After experimenting with physical cards, I turned to programming to explore its unusual properties and generate striking fractals.

The Perfect Shuffle Algorithm

The Perfect Shuffle reorders elements in an array in a remarkably simple way:

1. Divide the array into two equal halves.
2. Place elements from the first half into even positions and elements from the second half into odd positions.

JavaScript implementation (in‑shuffle)

function shuffle(array) {
    const half = array.length / 2;
    const temparray = [];
    for (let i = 0; i

For simplicity we focus on the in‑shuffle and assume arrays have an even number of elements (odd‑length arrays leave the last element static).

Periodicity

Because the algorithm is deterministic and the number of possible states is finite, repeated shuffling eventually returns the array to its original order. The required number of iterations is always ≤ the array length.

The sequence of iteration counts for arrays of length 2n is catalogued as A002326 in the OEIS. The following JavaScript computes it:

function a002326(n) {
    let a = 1, m = 0;
    do {
        a = (a * 2) % (2 * n + 1);
        m++;
    } while (a > 1);
    return m;
}
for (let n = 1; n < 11; n++) {
    console.log(a002326(n));
}

Reversal Property

For certain lengths the array’s order reverses after a specific number of iterations. Example: a 12‑element array reverses on the 6th iteration.

Visualizing the Shuffle

State‑space plot

• X‑axis: number of elements (divided by 2)
• Y‑axis: number of iterations needed to return to the start

The points appear chaotically distributed.

Binary pattern visualisation

Fill the first half of the array with 0s (black) and the second half with 1s (white). Each row represents the array’s state; rows are stacked for successive iterations. Examples:

• Arrays of 142–150 elements
• 288 elements (144 × 2)
• 610 elements

A small script (shuffle1d.html in the repository) generates these patterns. Enter the half‑size and click Draw.

Tracking a single element

The position of an element after each iteration can be computed directly:

x[n+1] = {
    x[n]/2 + y/2, if x[n] is even;
    (x[n] - 1)/2, if x[n] is odd;
}

where y is the array length. Plots for lengths 2–22 show unpredictable trajectories. Stacking many such trajectories yields fractal‑like images (clickable in the original article).

Extending to Matrices

Simple matrix tricks

1. Reverse the order of elements in the second half at each iteration.
2. Invert (swap) the elements in the second half.

These operations become useful when shuffling matrices.

Shuffling rows and columns

function shufflecr(array) {
    const half = array.length / 2;
    const temparray = [];

    for (let x = 0; x < half; x++) {
        temparray[x * 2] = [];
        temparray[x * 2 + 1] = [];
        for (let y = 0; y < half; y++) {
            temparray[x * 2][y * 2] = array[x + half][y + half];
            temparray[x * 2 + 1][y * 2] = array[x][y + half];
            temparray[x * 2][y * 2 + 1] = array[x + half][y];
            temparray[x * 2 + 1][y * 2 + 1] = array[x][y];
        }
    }
    return temparray;
}

This function shuffles both rows and columns simultaneously. Applying it to an 80 × 80 matrix produces intricate patterns; adding a second diagonal creates a moiré effect. Larger matrices (e.g., 242 × 242) reveal evolving structures over iterations 27–35.

Torus‑like behavior

When the matrix is treated as a torus (wrapping edges), edge effects become visible after just a few iterations.

Generating Fractals from the Shuffle

Morse–Thue sequence

By iteratively growing an array and shuffling with its inverted copy, the Morse–Thue sequence (OEIS A010060) emerges:

[1,0]
→ [1,0,0,1]
→ [0,1,1,0]
→ [0,1,1,0,1,0,0,1]
→ …

This binary sequence is a classic fractal.

Matrix‑based fractals

1. Copy the matrix.
2. Apply transformations (rotations, inversions).
3. Shuffle the original with the transformed copies.

Possible transformations (indexed 0‑15):

• 0: unchanged
• 1‑7: rotations (0°, 90°, 180°, 270°, etc.)
• 8‑15: inversions (mirrors)

Repeatedly applying a pattern such as 0, 0, 7, 7 (where action 7 rotates by 90°) yields a unique fractal after several iterations. Omitting the Perfect Shuffle while using the same actions produces a different, but still interesting, pattern.

Additional Visual Tricks

• Overlay a copy of the matrix with transparent white pixels, rotated 90°.
• Vertical rotation of the copy before overlaying.

These techniques further enrich the visual complexity achievable with the Perfect Shuffle.

All code snippets are provided with syntax‑highlighting hints. Links to OEIS sequences A002326 and A010060 are retained for reference.