역사
피셔-예이츠 셔플은 1938년 로널드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 통계 실험을 위한 종이 기반의 방법으로 처음 제안했다. 이들의 방법은 각 항목에 난수를 부여하고 난수 순서대로 항목을 정렬하는 방식이었다.
현대 컴퓨터 알고리즘 형태로 처음 구현된 것은 1964년 리처드 더스텐펠드(Richard Durstenfeld)에 의해서였으며, 그는 배열의 마지막 요소부터 시작하여 첫 번째 요소까지 역순으로 진행하는 현재 널리 알려진 방식을 제시했다. 이후 1969년 도널드 크누스(Donald Knuth)의 저서 'The Art of Computer Programming'에서 자세히 설명되며 널리 알려졌고, 이로 인해 '크누스 셔플(Knuth shuffle)'이라고도 불린다.
작동 원리
피셔-예이츠 셔플의 기본 원리는 집합의 요소를 처음부터 끝까지(또는 끝에서 처음까지) 순회하면서, 현재 요소와 아직 섞이지 않은(남아있는) 요소 중 하나를 무작위로 선택하여 서로 교환하는 것이다.
가장 일반적인 구현 방식은 다음과 같다:
- 길이가
n인 배열(또는 리스트)이 있다고 가정한다. - 배열의 마지막 요소(
n-1인덱스)부터 시작하여 첫 번째 요소(0인덱스)까지 역순으로 반복한다. 각 반복에서 현재 요소를i라고 한다. - 각
i에 대해0부터i까지의 범위(inclusive)에 있는 무작위 인덱스j를 선택한다. - 선택된 인덱스
j에 있는 요소와 현재 인덱스i에 있는 요소를 서로 교환한다. - 이 과정을
i가0이 될 때까지 반복한다.
예시 (마지막 요소부터 시작하는 방식):
- 초기 배열: [1, 2, 3, 4, 5]
- i = 4 (마지막 요소 5):
0부터4사이의 무작위 인덱스j를 선택한다.j = 2라고 가정하면, 배열은 [1, 2, 5, 4, 3]으로 바뀐다.
- i = 3 (현재 요소 4):
0부터3사이의 무작위 인덱스j를 선택한다.j = 0이라고 가정하면, 배열은 [4, 2, 5, 1, 3]으로 바뀐다.
- i = 2 (현재 요소 5):
0부터2사이의 무작위 인덱스j를 선택한다.j = 2라고 가정하면 (자기 자신과 교환), 배열은 [4, 2, 5, 1, 3]으로 그대로 유지된다.
- i = 1 (현재 요소 2):
0부터1사이의 무작위 인덱스j를 선택한다.j = 1이라고 가정하면 (자기 자신과 교환), 배열은 [4, 2, 5, 1, 3]으로 그대로 유지된다.
모든 과정이 끝나면, 배열은 무작위로 섞인 순열이 된다.
특징 및 장점
- 공정성(Unbiasedness): 모든 가능한 순열이 동일한 확률로 나타나도록 보장한다. 이는 각 단계에서 아직 섞이지 않은 요소 중에서만 무작위로 선택하여 교환하기 때문이다.
- 효율성(Efficiency): O(n)의 시간 복잡도를 가진다. 즉, 배열의 크기(n)에 선형적으로 비례하는 연산 횟수로 셔플이 완료되므로, 매우 효율적이다.
- 제자리(In-place) 작업: 추가적인 저장 공간 없이(O(1)의 공간 복잡도) 원본 배열 내에서 요소들의 위치만 바꾸어 셔플을 수행한다. 이는 메모리 사용량 측면에서 매우 효율적이다.
활용 분야
피셔-예이츠 셔플은 다음과 같은 다양한 분야에서 활용된다.
- 카드 게임: 트럼프 카드 덱이나 다른 카드 게임의 덱을 공정하게 섞는 데 사용된다.
- 통계적 샘플링: 모집단에서 무작위 표본을 추출해야 할 때, 편향되지 않은 표본을 얻기 위해 사용된다.
- 시뮬레이션: 다양한 경우의 수를 무작위로 생성하여 실험하거나 시뮬레이션을 수행할 때 유용하다.
- 무작위 데이터 생성: 시험 문제 순서 섞기, 플레이리스트 섞기 등 무작위 순서가 필요한 경우에 사용된다.
주의 사항
이 알고리즘의 공정성은 사용되는 난수 생성기(Random Number Generator, RNG)의 품질에 크게 의존한다. 부실하거나 편향된 난수 생성기는 피셔-예이츠 셔플이 의도한 공정하고 무작위적인 결과를 제공하지 못하고 편향된 순열을 초래할 수 있다. 따라서 보안이나 통계적 정확성이 중요한 애플리케이션에서는 암호학적으로 안전한 난수 생성기(Cryptographically Secure PRNG, CSPRNG)를 사용하는 것이 권장된다.