Perfect Shuffle: 간단한 알고리즘에 숨겨진 이상한 프랙털

Source: Dev.to

Introduction

저는 복잡한 패턴을 만들어내는 기본적인 알고리즘에 항상 매료되었습니다. 그 중 하나가 Perfect Shuffle(카드 마술사들 사이에서는 Faro Shuffle로 알려짐)입니다. 실제 카드를 가지고 실험한 뒤, 그 특이한 성질을 탐구하고 눈에 띄는 프랙탈을 생성하기 위해 프로그래밍으로 옮겼습니다.

The Perfect Shuffle Algorithm

Perfect Shuffle은 배열의 요소들을 놀라울 정도로 간단하게 재배열합니다:

1. 배열을 두 개의 같은 크기 절반으로 나눕니다.
2. 첫 번째 절반의 요소를 짝수 위치에, 두 번째 절반의 요소를 홀수 위치에 배치합니다.

JavaScript implementation (in‑shuffle)

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

간단히 말해 우리는 in‑shuffle에 집중하고, 배열 길이가 짝수라고 가정합니다(홀수 길이 배열은 마지막 요소가 고정됩니다).

Periodicity

알고리즘이 결정적이고 가능한 상태 수가 유한하기 때문에, 반복해서 셔플하면 결국 배열이 원래 순서로 돌아옵니다. 필요한 반복 횟수는 항상 배열 길이 이하입니다.

길이가 2n인 배열에 대한 반복 횟수 시퀀스는 OEIS에서 A002326으로 catalogued 되어 있습니다. 다음 JavaScript가 이를 계산합니다:

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

특정 길이에서는 일정 횟수 반복 후 배열 순서가 뒤집히기도 합니다. 예를 들어, 12요소 배열은 6번째 반복에서 뒤집힙니다.

Visualizing the Shuffle

State‑space plot

• X‑axis: 요소 개수 (절반으로 나눈 값)
• Y‑axis: 시작 상태로 돌아오는 데 필요한 반복 횟수

점들은 혼란스럽게 분포된 모습을 보입니다.

Binary pattern visualisation

배열 앞 절반을 0(검정), 뒤 절반을 1(흰색)으로 채웁니다. 각 행은 배열의 상태를 나타내며, 행들을 연속적인 반복에 따라 쌓습니다. 예시:

• 142–150 요소 배열
• 288 요소 (144 × 2)
• 610 요소

작은 스크립트(shuffle1d.html in the repository)가 이러한 패턴을 생성합니다. 절반 크기를 입력하고 Draw를 클릭하세요.

Tracking a single element

각 반복 후 특정 요소의 위치는 다음과 같이 직접 계산할 수 있습니다:

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

여기서 y는 배열 길이입니다. 길이 2–22에 대한 플롯은 예측 불가능한 궤적을 보여줍니다. 많은 궤적을 겹치면 프랙탈과 같은 이미지가 생성됩니다(원문 기사에서 클릭 가능).

Extending to Matrices

Simple matrix tricks

1. 각 반복마다 두 번째 절반의 요소 순서를 Reverse한다.
2. 두 번째 절반의 요소를 Invert(교환)한다.

이러한 연산은 행렬을 셔플할 때 유용합니다.

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;
}

이 함수는 행과 열을 동시에 셔플합니다. 80 × 80 행렬에 적용하면 복잡한 패턴이 나타나고, 두 번째 대각선을 추가하면 모아레 효과가 생깁니다. 더 큰 행렬(예: 242 × 242)에서는 27–35번째 반복 사이에 구조가 진화하는 모습을 볼 수 있습니다.

Torus‑like behavior

행렬을 토러스(가장자리 연결)처럼 취급하면 몇 번의 반복만에 가장자리 효과가 드러납니다.

Generating Fractals from the Shuffle

Morse–Thue sequence

배열을 점진적으로 확장하고, 그 반전 복사본과 셔플하면 Morse–Thue sequence(OEIS A010060)가 나타납니다:

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

이 이진 시퀀스는 고전적인 프랙탈입니다.

Matrix‑based fractals

1. 행렬을 복사한다.
2. 변환을 적용한다(회전, 반전).
3. 원본과 변환된 복사본을 셔플한다.

가능한 변환(인덱스 0‑15):

• 0: 그대로
• 1‑7: 회전(0°, 90°, 180°, 270° 등)
• 8‑15: 반전(미러)

예를 들어 0, 0, 7, 7(행동 7은 90° 회전)과 같은 패턴을 반복 적용하면 몇 차례 반복 후 독특한 프랙탈이 생성됩니다. 동일한 행동을 사용하되 Perfect Shuffle을 빼면 다른, 그래도 흥미로운 패턴이 나옵니다.

Additional Visual Tricks

• Overlay: 투명한 흰색 픽셀을 가진 행렬 복사본을 90° 회전시켜 겹친다.
• 복사본을 수직으로 회전한 뒤 겹친다.

이러한 기법은 Perfect Shuffle을 이용해 얻을 수 있는 시각적 복잡성을 더욱 풍부하게 해줍니다.

모든 코드 조각은 구문 강조 힌트와 함께 제공됩니다. OEIS 시퀀스 A002326 및 A010060에 대한 링크는 참고용으로 그대로 유지됩니다.