카드 N장을 섞는 프로그램이라면 가능한 N!개의 순서가 모두 같은 확률 1/N!로 나와야 공정합니다. 무작위 숫자를 여러 번 썼다는 사실만으로 이 조건이 저절로 성립하지는 않습니다. 피셔–예이츠 셔플(Fisher–Yates shuffle)은 아직 자리를 정하지 않은 구간에서 하나를 균등하게 골라 현재 끝자리와 교환하는 과정을 반복합니다. 난수 선택이 균등하다면 모든 순열을 정확히 같은 확률로 만드는 선형 시간 알고리즘입니다.
현대 배열용 피셔–예이츠 셔플 절차
길이 N인 0기반 배열 a가 있다고 하겠습니다. 인덱스 i를 N-1부터 1까지 줄입니다. 매 단계에서 0 이상 i 이하의 정수 j를 균등하게 하나 뽑고 a[i]와 a[j]를 교환합니다. j에 i 자체도 포함되는 것이 중요합니다. 같은 위치가 뽑히면 그 단계에서는 겉으로 아무 변화가 없지만, 원소가 원래 자리에 남는 순열도 다른 순열과 같은 자격을 가져야 합니다.
for i=N-1 down to 1: j를 {0,…,i}에서 균등 추출 → a[i]와 a[j] 교환
이 배열 내부 교환 방식은 1964년 Richard Durstenfeld가 Communications of the ACM에 발표한 Algorithm 235와 연결되어 설명되며, Donald Knuth가 널리 소개해 Knuth shuffle이라는 이름도 사용됩니다. Fisher와 Yates가 1938년에 제시한 원래 방식은 난수표를 사용해 남은 항목 중 하나를 골라 새 목록에 차례로 적는 종이·연필 절차였습니다. 핵심인 ‘남은 항목에서 균등하게 하나를 뽑는다’는 규칙은 같습니다.
5개 원소를 섞는 예
배열 [A,B,C,D,E]를 생각해 보겠습니다. i=4에서는 j를 0~4에서 골라 마지막 자리에 놓을 원소를 정합니다. 가령 j=1이면 B와 E를 바꿔 [A,E,C,D,B]가 되고 마지막 B는 확정됩니다. i=3에서는 아직 확정되지 않은 0~3 가운데 하나를 골라 네 번째 자리에 놓습니다. j=0이면 [D,E,C,A,B]가 됩니다. 이어 i=2, i=1에서도 같은 일을 하면 모든 자리가 정해집니다.
| 단계 i | j의 선택 범위 | 선택지 수 | 이번에 확정되는 자리 |
|---|---|---|---|
| 4 | 0~4 | 5 | 인덱스 4 |
| 3 | 0~3 | 4 | 인덱스 3 |
| 2 | 0~2 | 3 | 인덱스 2 |
| 1 | 0~1 | 2 | 인덱스 1 |
각 단계의 선택지 수를 곱하면 5×4×3×2=5!=120입니다. j 선택의 각 연속 기록은 하나의 최종 순열과 일대일로 대응합니다. 각 단계가 균등하고 난수 추출이 독립적이면 특정 선택 기록의 확률은 1/5×1/4×1/3×1/2=1/120입니다. 따라서 120개 순열이 모두 1/120 확률을 얻습니다.
왜 각 순열의 확률이 정확히 1/N!인가
특정 원소가 마지막 자리에 갈 확률은 N개 후보 중 하나이므로 1/N입니다. 마지막 자리가 정해진 뒤 남은 특정 원소가 그 앞자리에 갈 조건부 확률은 1/(N-1)입니다. 같은 논리를 첫 자리까지 이어 가면 정해진 순열 하나가 나올 확률은 다음과 같습니다.
1/N × 1/(N-1) × … × 1/2 × 1 = 1/N!
다르게 말하면 i번째 단계가 시작될 때 인덱스 0~i에는 아직 확정되지 않은 원소만 있습니다. 그중 하나를 균등하게 골라 i 자리에 고정하고 다시 건드리지 않습니다. 중복 없이 뽑는 표본추출을 배열 안에서 수행하는 셈입니다. 이 불변 조건이 끝까지 유지되기 때문에 모든 최종 순서가 균등합니다.
시간복잡도와 저장 공간
루프는 N-1번 돌고 각 단계에서 난수 하나와 교환 한 번을 수행하므로 시간복잡도는 Θ(N)입니다. 입력 배열을 직접 바꾸는 제자리 구현은 루프 변수와 임시 저장값 외에 배열 크기에 비례하는 추가 공간이 필요하지 않아 보조 공간 O(1)로 구현할 수 있습니다. 원본 배열을 보존하려면 먼저 복사해야 하므로 그 복사에 O(N) 시간과 공간이 듭니다.
잘못된 셔플 1: 매번 전체 구간에서 교환하기
겉보기에는 비슷하지만 i가 각 자리를 지날 때마다 j를 항상 0~N-1 전체에서 뽑는 구현은 일반적으로 균등하지 않습니다. N번 단계에서 각각 N개 선택을 하므로 난수 선택 경로가 Nᴺ개입니다. 모든 순열이 같은 횟수의 경로를 가져야 균등한데, N!이 Nᴺ을 나누지 않는 경우에는 애초에 같은 정수 개수로 배분할 수 없습니다.
N=3이면 전체 구간 교환법에는 3³=27개 선택 경로가 있지만 순열은 3!=6개입니다. 27은 6으로 나누어떨어지지 않으므로 각 순열에 똑같은 수의 경로를 배정할 수 없습니다. 반면 올바른 피셔–예이츠는 3×2=6개 선택 경로가 정확히 6개 순열에 하나씩 대응합니다.
잘못된 셔플 2: 무작위 키로 정렬하기
각 원소에 무작위 값을 붙여 정렬하는 방법은 키가 모두 서로 다르고 가능한 순서가 대칭적으로 처리되는 이상적 조건에서는 균등할 수 있습니다. 그러나 실제 난수 키의 범위는 유한하므로 동점이 생기고, 정렬 알고리즘이 동점을 처리하는 방식에 따라 원래 순서가 더 자주 남을 수 있습니다. 비교 함수가 호출될 때마다 새 난수를 반환하는 방식은 정렬 비교의 일관성도 깨뜨립니다. 실행 시간도 보통 O(N log N)이어서 O(N)인 피셔–예이츠보다 불필요하게 큽니다.
정수 난수 변환의 모듈로 편향
피셔–예이츠가 균등하다는 증명은 각 단계의 j가 범위 안에서 정확히 균등하다는 전제에 달려 있습니다. 난수 발생기가 0~99라는 100개 값을 균등하게 주는데 `% 16`으로 0~15를 만들면 100이 16으로 나누어떨어지지 않습니다. 나머지 0~3은 각각 7번, 4~15는 각각 6번 나타나 앞쪽 값이 더 자주 뽑힙니다.
이 편향은 거부 표본추출로 없앨 수 있습니다. 16으로 나누어떨어지는 가장 큰 범위인 0~95만 받아들이고 96~99가 나오면 다시 뽑습니다. 실제 프로그래밍 언어의 표준 난수 API가 범위 정수 생성을 제공한다면 그 함수의 규약을 확인해 쓰는 편이 안전합니다. 암호학적 용도의 카드 배분이나 추첨에는 예측 가능한 일반 의사난수 대신 목적에 맞는 안전한 난수원을 사용해야 합니다.
Math.random()×범위에서 확인할 점
0 이상 1 미만의 균등 실수 U가 이상적으로 주어진다면 floor(U×(i+1))은 0~i의 균등 정수를 만듭니다. 그러나 실제 U는 유한한 비트로 생성되므로 범위 크기가 난수 상태의 가능한 값 수와 잘 맞지 않으면 미세한 편향이 생길 수 있습니다. 배열 길이가 보통 범위에서는 영향이 작을 수 있지만, 보안이나 감사 가능한 추첨에서는 표준 암호 난수의 균등 범위 함수와 거부 표본추출을 사용합니다.
중복 값이 있는 배열은 어떻게 해석하나
피셔–예이츠는 배열의 위치, 즉 N개 항목의 순열을 균등하게 만듭니다. 값이 같은 원소가 여러 개면 서로 다른 위치 순열이 화면상 같은 값 배열로 보일 수 있습니다. 예를 들어 [A,A,B]에는 위치를 구분한 순열이 6개지만 관찰 가능한 값 순서는 AAB, ABA, BAA 세 가지이고 각각 두 위치 순열에 대응하므로 여전히 각 1/3입니다. 일반적으로 동일 값의 중복도를 고려해 결과를 해석해야 합니다.
부분 셔플로 k개만 뽑기
전체 N개 순서를 모두 만들 필요 없이 중복 없는 k개만 뽑는다면 피셔–예이츠의 k단계만 수행할 수 있습니다. 뒤쪽부터 k개 자리를 확정하거나 앞쪽 변형으로 k개를 확정하면 됩니다. 이 경우 선택된 순서까지 고려한 표본의 확률은 1/[N(N-1)…(N-k+1)]이고, 순서를 무시한 k개 집합은 모든 조합이 1/조합수(N,k)의 확률을 갖습니다. 원본 배열을 바꿀 수 있다는 조건에서는 O(k) 교환으로 끝납니다.
재현 가능한 테스트와 공정한 추첨은 목적이 다릅니다
프로그램 테스트에서는 같은 시드(seed)로 같은 셔플을 재현하면 오류를 추적하기 쉽습니다. 이때의 목적은 예측 불가능성이 아니라 반복 가능성입니다. 반대로 게임의 숨은 정보, 보안 토큰, 공개 추첨에서는 외부에서 결과를 예측하거나 시드를 알아낼 수 없어야 합니다. 셔플 알고리즘이 같아도 난수 발생기의 요구 조건은 용도에 따라 다릅니다.
구현 점검표
- i를 N-1부터 1까지 감소시키고 있는지 확인합니다.
- j의 범위가 0≤j≤i로 양 끝을 모두 포함하는지 확인합니다.
- j=i인 자기 자신과의 교환을 허용합니다.
- 각 단계에서 균등한 범위 정수를 생성하는지 확인합니다.
- 보안 목적이면 암호학적으로 안전한 난수원을 선택합니다.
- 원본 보존 여부와 중복 값의 의미를 명확히 정합니다.
- 작은 N에서는 모든 순열의 빈도를 반복 측정해 눈에 띄는 구현 편향을 검사할 수 있지만, 통계 검사가 수학적·보안적 정확성을 완전히 증명하는 것은 아닙니다.
피셔–예이츠 셔플 핵심 정리
피셔–예이츠 셔플은 아직 확정되지 않은 0~i 구간에서 j를 균등하게 하나 골라 i번째 원소와 교환합니다. 단계별 선택지 수 N, N-1, …, 2의 곱은 N!이고 각 선택 기록은 하나의 순열에 대응합니다. 그래서 올바른 난수 아래에서 각 순열의 확률은 정확히 1/N!입니다. 배열을 한 번 훑으므로 시간은 Θ(N), 제자리 구현의 보조 공간은 O(1)입니다.
공정성은 알고리즘 이름만으로 보장되지 않습니다. 전체 배열에서 매번 교환하는 변형, 무작위 비교 정렬, 끝점을 빠뜨린 범위, `%` 연산의 모듈로 편향, 예측 가능한 난수원은 결과를 치우치게 하거나 노출할 수 있습니다. 선택 구간과 난수의 균등성을 함께 지켜야 수학적 증명이 실제 코드에도 적용됩니다.