알고리즘 · LESSON 3
피셔·예이츠 - 응모자 섞기
가중치 추첨응모자들을 '진짜 공평하게' 섞어 순번(자리)을 정하는 방법이에요. 공평하다 = 모든 순서가 똑같은 확률로 나온다는 뜻이에요.
핵심은 딱 하나 — '남은 응모자 중 아무나'를 한 자리씩 정하는 거예요. 응모자가 자리를 옮기며 섞여요.
개념
그냥 막 섞으면 안 돼?
"응모자 둘을 골라 자리 바꾸기"를 여러 번 하면 될 것 같죠? 그런데 몇 번 해야 충분한지 아무도 모르고, 어떤 순서는 더 자주 나와서 공평하지 않을 수 있어요. 피셔·예이츠는 딱 한 바퀴로 완벽히 공평하게 끝내요.
개념
핵심 아이디어 — '자리를 하나씩 정하기'
자리(순번)가 5개 있어요. 맨 뒤 자리부터 "누가 이 자리에 앉을까?"를 정해요.
- 맨 뒤(5번째) 자리 → 5명 중 아무나 1명 (5가지)
- 그 앞(4번째) 자리 → 남은 4명 중 1명 (4가지)
- 3번째 자리 → 남은 3명 중 1명 … 이렇게 1번째까지
컴퓨터에선 뽑은 응모자를 그 자리 응모자와 '자리만 맞바꿔'요. 응모자가 자리를 옮기며 섞이는 거예요.
실험
한 자리씩 따라가기
지금 정하는 자리남은 후보방금 뽑힌 응모자확정된 자리
왜 공평할까
직접 세어보기
응모자 5명을 줄 세우는 방법은 5×4×3×2×1 = 120가지예요. 피셔·예이츠는 자리마다 '남은 응모자 중 아무나'라서 120가지 길이 생기고, 각 길이 서로 다른 순서를 딱 하나씩 만들어요 → 모든 순서가 정확히 1/120.
작은 3명(A·B·C)으로 보면 3×2×1 = 6가지예요.
| 가짓수 | 1번째 자리 | 2번째 자리 | 3번째 자리 |
|---|---|---|---|
| 1 | A | B | C |
| 2 | A | C | B |
| 3 | B | A | C |
| 4 | B | C | A |
| 5 | C | A | B |
| 6 | C | B | A |
6가지 순서가 딱 한 번씩 나오죠? 그래서 어떤 순서도 같은 확률 = 공평해요. (수천 번 돌려 확인은 아래 '1만 번 섞어 확인'에서)
검증
진짜 공평한지 — 여러 번 섞어 확인
"1번 응모자"가 각 자리에 앉은 횟수예요. 막대가 평평하면 공평한 거예요.
총 섞은 횟수 0
핵심 한 줄 — 맨 뒤 자리부터, 그 자리까지의 응모자 중 아무나 골라 자리를 맞바꾼다. 딱 한 바퀴면 끝, 모든 순서가 똑같은 확률이에요.
menu_book참고문헌
- Durstenfeld, R. (1964). Algorithm 235: Random Permutation. Communications of the ACM, 7(7), 420.
- Fisher–Yates Shuffle. Wikipedia. en.wikipedia.org/wiki/Fisher-Yates_shuffle