피셔-예이츠 셔플

피셔-예이츠 셔플의 Durstenfeld의 제자리 버전을 사용하여 5개의 문자를 섞는 예 **피셔-예이츠 셔플(Fisher-Yates shuffle)**은 유한 수열을 무작위 순열로 섞기 위한 알고리즘이다. 피셔-예이츠 셔플은 처음 기술한 로널드 피셔와 Frank Yates의 이름을 따서 명명되었으며 도널드 커누스의 이름을 따서 **커누스 셔플**이라고도 한다. **사톨로의 알고리즘**으로 알려진 피셔-예이츠 셔플의 변형을 사용하여 임의 순열 대신 길이가 *n* 인 임의 순환 순열 을 생성할 수 있다. 이 알고리즘은 모든 항목이 들어 있는 통에서 항목이 남아 있지 않을 때까지 항목을 무작위로 꺼내어 다음 항목을 선택한다. 이 알고리즘은 편향되지 않은 순열을 생성한다(모든 순열은 생성될 가능성이 동일하다).
# 피셔와 예이츠의 최초 방법
원래 형태의 피셔-예이츠 셔플은 1938년 로널드 피셔 와 Frank Yates 가 저서 *Statistical table for bio, Agriculture, Medical Research*에서 설명했다. oclc=14222135 Note: the 6th edition, , is available on the web, but gives a different shuffling algorithm by C. R. Rao. 여기서 알고리즘에 대한 설명은 연필과 종이를 사용했고 난수표의 난수를 사용했다. 1에서 *N* 까지의 임의 순열을 생성하는 기본 방법은 다음과 같다. # 1 부터 *N* 까지의 수를 쓴다. # 1과 지워지지 않고 남아 있는 수의 개수(포함) 사이의 임의의 수 *k*를 선택한다. # 작은 쪽부터 세어 아직 지워지지 않은 *k* 번째 수를 지워서 별도의 목록 끝에 적어둔다. # 모든 수가 지워질 때까지 2단계부터 반복한다. # 3단계에서 기록한 일련의 수가 임의 순열이 된다. 위의 2단계에서 선택한 임의의 수가 실제 난수이고 편향되지 않은 경우 결과 순열도 그렇게 된다. 피셔와 예이츠는 난수표에서 원하는 범위의 편향되지 않은 난수를 얻는 방법을 중요하게 설명하였다. 또한 1에서 *N* 까지의 난수를 선택하고 중복을 버리는 간단한 방법도 제안하고 있는데 이 방법을 앞쪽 절반에만 사용하고 나머지 절반에는 더 복잡한 알고리즘을 적용하도록 설명하였다. 만약 전체 순열에서 중복을 버리는 방법을 선택한다면 뒤쪽에서는 중복이 엄청나게 많아지게 되는 문제가 있다.
# 현대적인 알고리즘최신 버전의 알고리즘은 효율적이어서 섞는 항목 수에 비례하여 시간이 걸리고 제자리에서 섞는다.
컴퓨터용으로 설계된 피셔-예이츠 셔플의 최신 버전은 1964년 Richard Durstenfeld 에 의해 소개되었고doi=10.1145/364520.364540 도널드 커누스 가 *The Art of Computer Programming* 에서 "알고리즘 P(셔플링)"로 소개하여 널리 알려졌다. oclc=85975465 Durstenfeld의 글과 커누스의 *Art of Computer Programming* 초판 모두 피셔와 예이츠의 작업을 알리지 않았지만 그들은 그것을 알지 못했을 수 있다. 커누스의 *Art of Computer Programming* 의 후속 판에서는 피셔와 예이츠의 공헌에 대해 언급하고 있다. oclc=38207978 Durstenfeld가 설명한 알고리즘은 피셔와 예이츠가 제공한 알고리즘과 작지만 중요한 부분이 다르다. 피셔와 예이츠 방법를 그대로 구현한 것은 위의 3단계에서 나머지 숫자를 계산하는 데 불필요한 시간을 소비하지만 Durstenfeld의 솔루션은 선택된 숫자를 각각의 마지막으로 지워지지 않은 숫자로 교체하여 목록의 끝으로 이동하는 것을 반복한다. 이것은 알고리즘의 시간 복잡도를 기본 구현인 \mathcal{O}(n^2)에서 \mathcal{O}(n)으로 낮춘다. 확인날짜=2007-08-09 이 변경이 적용된 알고리즘은 아래와 같다. \-- *n*개의 요소(인덱스 0..*n*-1)의 배열을 섞기: **for** *i* **from** *n*−1 **downto** 1 **do** *j* ← 0 ≤ *j* ≤ *i*인 임의의 정수 *a*[*j*]와 *a*[*i*] 교환 배열을 반대 방향(가장 낮은 인덱스에서 가장 높은 인덱스로)으로 섞는 같은 동작을 하는 알고리즘은 다음과 같다. \-- *n*개의 요소(인덱스 0.. *n* -1)의 배열을 섞기: **for** *i* **from** 0 **to** *n*−2 **do** *j* ← *i* ≤ *j* DABC -> CDAB -> **BCDA** -> ABCD. . . |- | **DABC** | ABCD -> BCDA -> CDAB -> **DABC** -> ABCD. . . |- | **BDAC** | ABCD -> CADB -> DCBA -> **BDAC** -> ABCD. . . |- | **CADB** | ABCD -> BDAC -> DCBA -> **CADB** -> ABCD. . . |- | **CDBA** | ABCD -> DCAB -> BADC -> **CDBA** -> ABCD. . . |- | **DCAB** | ABCD -> CDBA -> BADC -> **DCAB** -> ABCD. . . |- | colspan="2" | 사톨로 알고리즘으로 생성된 ABCD의 여섯(3!) 가지 순환 순열 |} 매우 유사한 알고리즘이 (최대) 길이 *n*의 균일하게 분포된 사이클 을 생성하기 위해 샌드라 사톨로(Sandra Sattolo) 에 의해 1986년에 발표되었다. doi=10.1016/0020-0190(86)90073-6 Durstenfeld와 사톨로 알고리즘 사이의 유일한 차이점은 후자의 경우 위의 2단계에서 난수 *j* 가 1과 *i* -1(1과 *i* 가 아닌) 범위에서 선택된다는 것이다. 이 간단한 변경은 결과 순열이 항상 단일 주기로 구성되도록 알고리즘을 수정한다. 실제로 아래에서 설명하는 것처럼 일반적인 피셔-예이츠 셔플을 구현하려고 할 때 *실수로* 사톨로의 알고리즘을 구현하게 되기 매우 쉽다. 이는 *n*! 개의 전체 순열 집합이 아니라 (*n* −1)! 개의 더 작은 집합에서 선택되도록 하여 결과를 편향시킨다. 사톨로 알고리즘을 파이선에서 구현한 것은 다음과 같다. from random import randrange def sattolo_cycle(items) -> None: """Sattolo's algorithm.""" i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j]
# 참고 문헌(각주)
각주