피셔-예이츠 셔플

피셔-예이츠 셔플(Fisher-Yates shuffle)은 유한 수열을 무작위 순열로 섞기 위한 알고리즘이다.

피셔–예이츠 셔플의 Durstenfeld의 제자리 버전을 사용하여 5개의 문자를 섞는 예

피셔-예이츠 셔플은 처음 기술한 로널드 피셔와 Frank Yates의 이름을 따서 명명되었으며 도널드 커누스의 이름을 따서 커누스 셔플이라고도 한다. 사톨로의 알고리즘으로 알려진 피셔-예이츠 셔플의 변형을 사용하여 임의 순열 대신 길이가 n 인 임의 순환 순열 을 생성할 수 있다.

이 알고리즘은 모든 항목이 들어 있는 통에서 항목이 남아 있지 않을 때까지 항목을 무작위로 꺼내어 다음 항목을 선택한다. 이 알고리즘은 편향되지 않은 순열을 생성한다(모든 순열은 생성될 가능성이 동일하다).

피셔와 예이츠의 최초 방법

원래 형태의 피셔-예이츠 셔플은 1938년 로널드 피셔 와 Frank Yates 가 저서 Statistical table for bio, Agriculture, Medical Research에서 설명했다. 여기서 알고리즘에 대한 설명은 연필과 종이를 사용했고 난수표의 난수를 사용했다. 1에서 N 까지의 임의 순열을 생성하는 기본 방법은 다음과 같다.

1. 1 부터 N 까지의 수를 쓴다.
2. 1과 지워지지 않고 남아 있는 수의 개수(포함) 사이의 임의의 수 k를 선택한다.
3. 작은 쪽부터 세어 아직 지워지지 않은 k 번째 수를 지워서 별도의 목록 끝에 적어둔다.
4. 모든 수가 지워질 때까지 2단계부터 반복한다.
5. 3단계에서 기록한 일련의 수가 임의 순열이 된다.

위의 2단계에서 선택한 임의의 수가 실제 난수이고 편향되지 않은 경우 결과 순열도 그렇게 된다. 피셔와 예이츠는 난수표에서 원하는 범위의 편향되지 않은 난수를 얻는 방법을 중요하게 설명하였다. 또한 1에서 N 까지의 난수를 선택하고 중복을 버리는 간단한 방법도 제안하고 있는데 이 방법을 앞쪽 절반에만 사용하고 나머지 절반에는 더 복잡한 알고리즘을 적용하도록 설명하였다. 만약 전체 순열에서 중복을 버리는 방법을 선택한다면 뒤쪽에서는 중복이 엄청나게 많아지게 되는 문제가 있다.

현대적인 알고리즘

컴퓨터용으로 설계된 피셔-예이츠 셔플의 최신 버전은 1964년 Richard Durstenfeld 에 의해 소개되었고 도널드 커누스 가 The Art of Computer Programming 에서 "알고리즘 P(셔플링)"로 소개하여 널리 알려졌다. Durstenfeld의 글과 커누스의 Art of Computer Programming 초판 모두 피셔와 예이츠의 작업을 알리지 않았지만 그들은 그것을 알지 못했을 수 있다. 커누스의 Art of Computer Programming 의 후속 판에서는 피셔와 예이츠의 공헌에 대해 언급하고 있다.

Durstenfeld가 설명한 알고리즘은 피셔와 예이츠가 제공한 알고리즘과 작지만 중요한 부분이 다르다. 피셔와 예이츠 방법를 그대로 구현한 것은 위의 3단계에서 나머지 숫자를 계산하는 데 불필요한 시간을 소비하지만 Durstenfeld의 솔루션은 선택된 숫자를 각각의 마지막으로 지워지지 않은 숫자로 교체하여 목록의 끝으로 이동하는 것을 반복한다. 이것은 알고리즘의 시간 복잡도를 기본 구현인 ${\mathcal {O}}(n^{2})$에서 ${\mathcal {O}}(n)$으로 낮춘다. 이 변경이 적용된 알고리즘은 아래와 같다.

-- 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 < n인 임의의 정수
     a[i]와 a[j] 교환

예

연필과 종이 방법

예를 들어 피셔와 예이츠의 최초 방법 을 사용하여 A부터 H까지 문자를 섞어보자. 다음과 같이 종이에 글자를 쓰는 것으로 시작한다.

범위	난수	종이	결과
		A B C D E F G H

이제 1부터 8까지 중 임의의 숫자 k가 3으로 나왔다고 하자. 그리고 종이에 k 번째(즉, 세 번째) 문자를 지우고 결과에 기록한다.

범위	난수	종이	결과
1–8	3	A B C D E F G H	C

이제 두 번째 난수를 선택합니다. 이번에는 1부터 7까지입니다. 결과가 4가 나왔다고 하자. 이제 종이에서 아직 지워지지(취소선) 않은 네 번째 문자(문자 E)를 지우고 결과에 추가한다.

범위	난수	종이	결과
1–7	4	A B C D E F G H	C E

이제 다음 난수를 1부터 6까지 중에서 선택하고, 그 다음은 1부터 5까지, 등등 계속해서 위와 같이 지우는 과정을 반복한다.

범위	난수	종이	결과
1–6	5	A B C C E F G H	C E G
1–5	3	A B C D E F G H	C E G D
1–4	4	A B C D E F G H	C E G D H
1–3	1	A B C D E F G H	C E G D H A
1–2	2	A B C D E F G H	C E G D H A F
		A B C D E F G H	C E G D H A F B

현대적인 방법

이제 Durstenfeld의 알고리즘 버전 을 사용하여 동일한 작업을 수행해 보자. 이번에는 선택한 문자를 지우고 다른 곳에 복사하는 대신 아직 선택되지 않은 마지막 문자로 교체한다. 이전과 같이 A에서 H까지의 문자를 쓰는 것으로 시작한다.

범위	난수	종이	결과
		A B C D E F G H

첫 번째 선택에서는 1에서 8까지 중 임의의 숫자를 선택한다. 이번에는 6이라고 치고 목록에서 6번째와 8번째 문자를 바꾼다.

범위	난수	종이	결과
1–8	6	A B C D E H G	F

다음 난수는 1에서 7까지 중에 2가 선택되었다고 하자. 따라서 두 번째와 일곱 번째 문자를 바꾸고 계속 진행한다.

범위	난수	종이	결과
1–7	2	A G C D E H	B F

다음 난수는 1에서 6이며, 6이 나왔다고 하자. 목록의 6번째 문자 H가 현재 선택되지 않은 마지막 글자이므로 교환 후에도 그대로이다. 그리고, 순열이 완료될 때까지 같은 방식으로 계속 진행한다.

범위	난수	종이					결과
1–6	6	A G C D E					H B F
1–5	1	E G C D				A H B F
1–4	3	E G D			C A H B F
1–3	3	E G		D C A H B F
1–2	1	G	E D C A H B F

이 시점에서 더 이상 수행할 수 있는 것은 없으므로 결과 순열은 G E D C A H B F이다.

사톨로(Sattolo) 알고리즘

순환되는 순열	예시
BCDA	ABCD → 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. . .
사톨로 알고리즘으로 생성된 ABCD의 여섯(3!) 가지 순환 순열

매우 유사한 알고리즘이 (최대) 길이 n의 균일하게 분포된 사이클 을 생성하기 위해 샌드라 사톨로(Sandra Sattolo) 에 의해 1986년에 발표되었다. 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]

같이 보기

• RC4, 배열 셔플링 기반의 스트림 암호화
• 저수지 샘플링, 피셔-예이츠 셔플의 특별한 경우인 알고리즘 R 부분

외부 링크

• 대화식 예제