피셔–예이츠 셔플 (Fisher–Yates Shuffle)

카드 N장을 섞을 때, 나올 수 있는 N!가지 순서가 모두 똑같은 확률로 나와야 "공정한" 셔플이다. 언뜻 떠오르는 방법 — 각 칸을 아무 칸이나와 맞바꾸기 — 은 사실 편향돼 있다. 피셔–예이츠는 뒤에서부터 0..i 범위에서만 뽑아 맞바꿔, O(n)에 완벽히 균일한 순열을 만든다.

1. 한 단계씩 섞어보기

뒤에서부터 커서(주황) 위치 i를 잡고, 0 ~ i 중 무작위 한 장(파랑)을 골라 맞바꾼다. 확정된 칸은 초록.

2. 편향 실험 — 잘못된 셔플 vs 피셔–예이츠

카드 수 N

5장

잘못된 셔플 편향

가로: 최종 위치 · 세로: 처음 카드 · 색이 진할수록 자주 등장

피셔–예이츠 균일

모든 칸이 1/N 근처의 회색 = 완전 균일

기대 확률 (1/N)

20.0%

잘못된 셔플 최대 편차

–

피셔–예이츠 최대 편차

–

잘못된 셔플은 총 N^N가지 실행 경로가 N!가지 결과에 고르게 나뉘지 않는다 (예: N=3이면 27경로 ÷ 6결과 = 4.5 → 정수가 안 됨). 그래서 어떤 카드는 특정 위치에 더 자주 남는다.

3. 알고리즘 비교 (의사코드)

# ❌ 잘못된 방법 — 범위가 항상 0..n-1 (편향!)
def naive_shuffle(a):
    n = len(a)
    for i in range(n):
        j = random(0, n - 1)      # 이미 지나온 칸도 다시 건드림
        a[i], a[j] = a[j], a[i]

# ✅ 피셔–예이츠 — 범위를 0..i 로 좁혀 간다
def fisher_yates(a):
    for i in range(len(a) - 1, 0, -1):
        j = random(0, i)          # 아직 안 정해진 칸에서만 뽑기
        a[i], a[j] = a[j], a[i]   # i 자리 확정

# 시간 O(n) · 추가 메모리 O(1) · 결과: N! 순열이 정확히 균일

핵심 차이는 딱 한 글자: 뽑는 범위가 random(0, n-1)이냐 random(0, i)이냐다. 언어 표준 라이브러리의 shuffle()(파이썬 random.shuffle, JS 라이브러리 등)은 모두 피셔–예이츠다.

4. 핵심 정리

공정한 셔플

N!가지 순서가 모두 1/N! 확률. 이걸 만족해야 뽑기·카드게임이 공평하다.

잘못된 직관

"모든 칸을 아무 칸이나와 바꾸기"는 N^N ≠ N! 이라서 편향된다.

피셔–예이츠

뒤에서부터 0..i 범위로 좁혀 뽑는다. 각 원소가 각 자리에 갈 확률이 정확히 1/N.

성능

한 번의 순회로 끝 — O(n) 시간, O(1) 추가 메모리. 정렬(O(n log n))보다 빠르다.

난수 품질

결과는 난수 생성기 만큼만 공정하다. 카지노·암호용은 CSPRNG를 써야 한다.

응용

카드 섞기, 랜덤 문제 출제, A/B 그룹 배정, 데이터 증강, 몬테카를로 표본 추출.