피셔-예이츠 셔플

피셔-예이츠 셔플(Fisher–Yates shuffle)은 유한한 개수의 항목을 임의의 순서로 재배열하는 알고리즘이다. 모든 가능한 순열이 동일한 확률로 생성되도록 보장하는 특징을 가지며, 난수 생성기를 기반으로 동작한다.

역사

이 알고리즘은 1938년 로널드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 통계표 작성을 위한 표본 무작위화 방법으로 제안하였다. 당시에는 수작업용으로 고안되었으며, 이후 1964년 리처드 더스널(Richard Durstenfeld)이 컴퓨터 구현에 적합한 형태로 재구성하였다. 도널드 커누스(Donald Knuth)는 이 알고리즘을 《The Art of Computer Programming》에서 소개하며 널리 보급시켰다.

알고리즘

피셔-예이츠 셔플의 동작은 다음과 같다.

1. 길이 n인 배열 A를 입력으로 받는다.
2. i를 n−1부터 1까지 감소시키며 반복한다.
3. 정수 j를 무작위로 선택하되, 0 ≤ j ≤ i를 만족해야 한다.
4. A[i]와 A[j]의 값을 교환한다.

이 과정은 총 n−1회 반복되며, 각 반복마다 교환이 한 번 발생한다. 이 알고리즘은 제자리(in-place) 방식으로 동작하며, 별도의 메모리를 사용하지 않는다.

의사코드

for i from n - 1 downto 1 do
    j ← random integer such that 0 ≤ j ≤ i
    swap A[i] with A[j]

파이썬 예시

다음은 피셔-예이츠 셔플의 파이썬 구현 예시이다.

import random

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

# 예시 실행
if __name__ == "__main__":
    random.seed(42)  # 재현 가능성을 위한 시드 설정
    data = [1, 2, 3, 4, 5]
    print("셔플 전:", data)
    fisher_yates_shuffle(data)
    print("셔플 후:", data)

이 예제는 배열 [1, 2, 3, 4, 5]를 무작위로 섞으며, 시드를 고정함으로써 동일한 셔플 결과를 재현할 수 있다. 실제 실행 결과는 다음과 유사하다.

• 셔플 전: [1, 2, 3, 4, 5]
• 셔플 후: [4, 2, 5, 1, 3]

수학적 정당성

피셔-예이츠 셔플은 n개의 원소에 대해 n!개의 가능한 순열 중 정확히 하나를 균등한 확률(1/n!)로 생성한다. 이는 각 단계에서 선택된 인덱스가 가능한 범위 내에서 균등하게 선택되며, 이후 단계의 선택에 영향을 미치지 않기 때문에 조건부 확률에 따라 전 범위가 동일하게 분포함을 증명할 수 있다.

구현상의 주의점

많은 구현에서 다음과 같은 실수가 발생할 수 있다.

• 무작위 인덱스 범위 오류: j를 i보다 큰 범위에서 선택하면 순열 분포가 왜곡된다.
• 비균등 난수 생성기 사용: 낮은 품질의 의사 난수 생성기를 사용할 경우 특정 순열이 과도하게 많이 발생할 수 있다.
• 선택 인덱스의 오프셋: random.randint(0, i) 대신 random.randint(1, i)로 구현하면 치명적인 편향이 발생한다.

변형 알고리즘

온라인 셔플링

자료를 순차적으로 수신하면서 동적으로 섞는 변형이 가능하다. 이는 스트리밍 데이터 환경에서 사용된다. 다음은 그 구현 개요이다.

1. 배열 A에 데이터를 하나씩 추가하며 처리한다.
2. 새로 들어온 A[i]와 A[j]를 교환하되, j는 0 ≤ j ≤ i인 무작위 인덱스이다.

이 방식은 기존 데이터를 모두 메모리에 유지하지 않고도 무작위화를 수행할 수 있어 메모리 제약 환경에서 유용하다.

특성

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)
• 모든 순열이 균등한 확률로 생성됨
• 제자리(in-place) 알고리즘

응용

• 카드 셔플링
• 무작위 샘플링
• 게임에서 아이템 드롭 순서 결정
• 통계 시뮬레이션 및 부트스트래핑
• 테스트용 데이터 무작위화

같이 보기

• 난수 생성기
• 정렬 알고리즘
• 모의 실험
• 통계학
• 표본 추출

참고 문헌

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
• Fisher, R. A., & Yates, F. (1938). Statistical Tables for Biological, Agricultural and Medical Research. Oliver & Boyd.
• Durstenfeld, R. (1964). Algorithm 235: Random permutation. Communications of the ACM, 7(7), 420.