피셔-예이츠 셔플

3. 알고리즘

3. 1. 피셔와 예이츠의 방법

위 표는 1–8 의 숫자를 섞는 예시를 보여준다.

3. 2. 현대적인 방법 (더스텐펠드 알고리즘)

• 배열 a[0..n-1]을 섞는다.

• 0 ≤ j ≤ i 인 무작위 정수 j를 선택한다.
• a[j]와 a[i]를 교환한다.

위 표와 같이, 각 단계에서 선택된 문자와 아직 선택되지 않은 마지막 문자를 교환한다. 최종적으로 G E D C A H B F 순열을 얻는다.

다른 구현 방식으로는 다음과 같이 배열의 앞쪽에서부터 셔플을 진행할 수도 있다.

• 배열 a[0..n-1]을 섞는다.

• i ≤ j < n 인 무작위 정수 j를 선택한다.
• a[j]와 a[i]를 교환한다.

3. 3. "인사이드-아웃" 알고리즘

3. 4. 사톨로 알고리즘 (Sattolo's algorithm)

사톨로 알고리즘은 수학적 귀납법을 통해 길이 ''n''의 사이클을 생성함을 증명할 수 있다. 초기 반복 후, 나머지 반복이 처음 ''n'' − 1개 요소를 길이 ''n'' − 1의 사이클에 따라 순열한다고 가정한다. 초기 요소를 새로운 위치 ''p''로 추적하고, 원래 위치 ''p''의 요소를 새로운 위치로 추적하는 방식으로, 다른 모든 위치를 방문한 후에 초기 위치로 돌아온다.

사톨로 알고리즘은 (''n''−1)!개의 고유한 가능한 난수 시퀀스를 가지며, 각 시퀀스는 서로 다른 순열을 생성한다. 난수 소스가 편향되지 않았다고 가정하면 각 순열은 동일한 확률로 발생한다. 이렇게 생성된 (''n''−1)!개의 서로 다른 순열은 길이 ''n''의 사이클 집합을 모두 포함한다.

파이썬으로 구현된 사톨로 알고리즘의 예는 다음과 같다:



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]



일반적인 피셔-예이츠 셔플을 구현할 때, 의도치 않게 사톨로 알고리즘을 구현하는 경우가 발생할 수 있다. 이는 ''n''! 개의 전체 순열 집합이 아닌 (''n'' −1)! 개의 더 작은 집합에서 선택되도록 하여 결과를 편향시킨다.

4. 예시

4. 1. 연필과 종이 방법 (피셔-예이츠)

그런 다음 1부터 8까지의 숫자 중 임의의 숫자 k를 선택한다. 예를 들어 k가 3이라고 하자. 종이에 k번째(즉, 세 번째) 문자를 지우고 결과에 기록한다.

이제 1부터 7까지의 범위에서 두 번째 난수를 선택한다. 예를 들어 4가 나왔다면, 아직 지워지지 않은 네 번째 문자(E)를 지우고 결과에 추가한다.

이후 1부터 6, 1부터 5와 같이 범위를 줄여가며 위 과정을 반복한다. 매번 선택된 문자를 지우고 결과에 추가하는 방식으로 진행하여, 모든 문자가 지워질 때까지 반복하면 무작위 순열이 완성된다.

이와 같은 방식으로 숫자, 문자 등 다양한 대상을 섞을 수 있다.

4. 2. 현대적인 방법 (더스텐펠드)

처음에는 1-8 범위에서 난수를 생성하여, 해당 위치의 문자와 마지막 문자를 교환한다. 예를 들어 난수가 6이면 6번째 문자인 F와 8번째 문자인 H를 교환한다. 다음 단계에서는 1-7 범위에서 난수를 생성하여, 해당 위치의 문자와 7번째 문자를 교환한다. 위 표에서는 난수 2가 생성되어, 2번째 문자인 B와 7번째 문자인 G가 교환되었다. 이러한 방식으로 마지막 단계까지 반복하여 최종 순열을 얻는다.

위의 예시와 동일한 과정을 숫자에도 적용할 수 있다. 1부터 8까지의 숫자를 사용하여 동일한 방식으로 셔플을 진행한다.

최종적으로 "7 5 4 3 1 8 2 6" 순열을 얻게 된다. 이처럼 더스텐펠드의 알고리즘은 각 단계에서 선택되지 않은 요소 중 마지막 요소와 현재 선택된 요소를 교환하는 간단한 과정을 통해 효율적인 셔플을 구현한다.

5. 구현 예시

피셔-예이츠 셔플은 파이썬과 자바스크립트 등 다양한 프로그래밍 언어로 구현할 수 있다.

다음은 파이썬을 사용한 피셔-예이츠 셔플의 구현 예시이다.

```python

import random

def shuffle(n: int) -> list[int]:

numbers = list(range(n))

shuffled = []

while numbers:

k = random.randint(0, len(numbers) - 1)

shuffled.append(numbers[k])

numbers.pop(k)

return shuffled

```

다음은 자바스크립트를 사용한 피셔-예이츠 셔플의 구현 예시이다.

```javascript

function shuffleArray(array) {

for (let i = array.length - 1; i >= 0; i--) {

const j = Math.floor(Math.random() * (i + 1));

[array[i], array[j]] = [array[j], array[i]];

}

}

6. 변형 알고리즘

6. 1. 병렬 알고리즘

6. 2. k개의 요소 선택

7. 다른 셔플 알고리즘과의 비교

피셔-예이츠 셔플은 시간 및 공간 복잡도 면에서 최적이며, 양질의 편향되지 않은 난수 소스와 결합하면 편향되지 않은 결과를 생성하는 것이 보장된다.<sup>[13]</sup> 또한, 결과 순열의 일부만 필요한 경우 중간에 중단하거나, 반복적으로 중단 및 재시작하여 필요에 따라 순열을 점진적으로 생성할 수 있다는 장점이 있다.

다른 셔플 알고리즘과 비교했을 때, 각 요소를 무작위로 선택된 다른 요소와 바꾸는 단순한 방법(Naive method)은 편향된 결과를 생성한다.<sup>[13]</sup> 이는 서로 다른 순열의 수($n!$)가 알고리즘의 무작위 결과의 수($n^n$)를 균등하게 나누지 않기 때문이다. 예를 들어, 베르트랑의 가설에 따르면 $n/2$와 $n$ 사이에 적어도 하나의 소수가 존재하며, 이 수는 $n!$을 나누지만 $n^n$을 나누지 않는다.

또 다른 방법은 셔플할 집합의 각 요소에 임의의 숫자를 할당한 다음, 할당된 숫자에 따라 집합을 정렬하는 것이다. 이 방법은 피셔-예이츠 셔플과 동일한 점근적 시간 복잡도를 가지며, 기수 정렬을 사용하면 ''O''(''n'') 시간에 효율적으로 정렬할 수 있다. 또한, 이 방법은 편향되지 않은 결과를 생성한다.<sup>[14]</sup> 그러나 할당된 임의 숫자가 중복되지 않도록 주의해야 하며,<sup>[32]</sup> 추가 저장 공간 ''O''(''n'')이 필요하다는 단점이 있다. 반면 피셔-예이츠 셔플은 ''O''(1)의 공간만을 사용한다. 정렬 방법은 병렬 알고리즘 구현이 가능하다는 장점이 있다.

사용자 지정 비교 함수로 정렬을 지원하는 언어에서, 임의의 값을 반환하는 비교 함수로 정렬하여 셔플하는 방법도 사용될 수 있다. 그러나 이 방법은 매우 비균일한 분포를 생성할 가능성이 높으며,<sup>[15][16][33][34][35]</sup> 사용된 정렬 알고리즘에 크게 의존한다.<sup>[36]</sup> 예를 들어, 퀵 정렬에서 첫 번째 피벗 요소를 고정된 요소로 사용하는 경우, 피벗 요소의 최종 위치는 이항 분포를 따르게 되어 시퀀스 중앙에 위치할 확률이 높아진다. 병합 정렬과 같은 다른 정렬 방법을 사용하더라도, 두 시퀀스를 선택할 확률이 균일하지 않으면 완전한 균일 분포를 얻기 어렵다.

8. 잠재적인 편향 발생 원인

피셔-예이츠 셔플을 구현할 때, 알고리즘 자체의 구현과 이를 기반으로 하는 난수 생성 모두에 주의를 기울여야 한다. 그렇지 않으면 결과에 감지 가능한 편향이 나타날 수 있다. 다음은 편향이 발생하는 대표적인 요인이다.

== 구현 오류 ==

피셔-예이츠 셔플을 구현할 때 흔히 저지르는 오류는 가져올 난수의 범위를 잘못 설정하는 것이다.<sup>[37]</sup> 잘못된 알고리즘이 제대로 작동하는 것처럼 보일 수 있지만, 모든 가능한 순열을 동일한 확률로 생성하지 않으며, 특정 순열을 전혀 생성하지 못할 수도 있다. 예를 들어, 교체할 항목의 인덱스 ''j''를 교체될 항목의 인덱스 ''i''보다 항상 엄격하게 작게 선택하는 오프 바이 원 오류가 발생하면 피셔-예이츠 셔플이 사톨로 알고리즘으로 바뀐다. 이 경우 얻을 수 있는 순열은 원순열뿐이며, 모든 요소는 원래 위치에 배치되지 않는다.<sup>[37]</sup>

마찬가지로, ''모든'' 반복에서 유효한 배열 인덱스의 전체 범위에서 항상 ''j''를 선택하는 것도 편향된 결과를 생성한다. 이는 ''n''<sup>''n''</sup>개의 서로 다른 가능한 교체 시퀀스가 생성되지만, ''n''개 요소 배열의 가능한 순열은 ''n''!개뿐이라는 사실에서 알 수 있다. ''n''<sup>''n''</sup>은 ''n''!로 균등하게 나눌 수 없으므로, 일부 순열은 다른 순열보다 더 많이 생성되어야 한다.

예를 들어, 3개 요소 배열 [1, 2, 3]을 섞었을 때 가능한 순열은 6개(3! = 6)이지만, 알고리즘은 27개(3<sup>3</sup> = 27)의 가능한 셔플을 생성한다. 이 경우, [1, 2, 3], [3, 1, 2], [3, 2, 1]은 각각 27개의 셔플 중 4개에서 생성되는 반면, 나머지 3개의 순열은 각각 27개의 셔플 중 5번 나타난다.<sup>[37]</sup>

길이가 7인 목록에서 각 요소가 다른 위치에 놓일 확률을 보여주는 행렬을 보면, 대부분의 요소에서 원래 위치(행렬의 주 대각선)에 있는 확률이 가장 낮고, 한 칸 뒤로 이동하는 확률이 가장 높다는 것을 알 수 있다.<sup>[37]</sup>

== 모듈로 편향 (Modulo bias) ==

대부분의 난수 생성기는 — 참이든 의사 난수이든 — 0에서 RAND_MAX까지의 고정된 범위의 숫자만 직접 제공하며, 일부 라이브러리에서는 RAND_MAX가 32767까지 낮을 수 있다.<sup>[18]</sup> 이러한 숫자를 원하는 범위로 강제하는 간단하고 일반적으로 사용되는 방법은 나머지 연산자를 적용하는 것이다.<sup>[19]</sup> 즉, 난수를 범위의 크기로 나누고 나머지를 구하는 것이다. 그러나 피셔-예이츠 셔플에서 0–1에서 0–''n''까지의 모든 범위에서 난수를 생성해야 하므로 이러한 범위 중 일부가 난수 생성기의 자연 범위를 균등하게 나누지 못할 가능성이 거의 확실하다. 따라서 나머지가 항상 균등하게 분포되지 않으며, 더 나쁜 것은 바이어스가 작은 나머지를 선호하는 방향으로 체계적으로 나타난다는 것이다.<sup>[20]</sup>

예를 들어, 난수 소스가 0에서 99까지의 숫자를 제공한다고 가정해 보자.(이는 100개의 값이다.) 그리고 0에서 15(16개 값)까지의 바이어스 없는 난수를 얻고 싶다고 가정해 보자. 단순히 숫자를 16으로 나누고 나머지를 구하면 0–3의 숫자가 다른 숫자보다 약 17% 더 자주 발생한다는 것을 알 수 있다. 이는 16이 100을 균등하게 나누지 않기 때문이다. 100보다 작거나 같은 16의 가장 큰 배수는 6×16 = 96이며, 바이어스를 유발하는 것은 불완전한 범위 96–99의 숫자이다. 이 문제를 해결하는 가장 간단한 방법은 나머지를 구하기 전에 해당 숫자를 버리고 적절한 범위의 숫자가 나올 때까지 다시 시도하는 것이다.<sup>[21]</sup> 원칙적으로 최악의 경우 영원히 걸릴 수 있지만, 재시도 기대값은 항상 1보다 작다.

관련된 문제는 먼저 임의의 부동 소수점 숫자를 생성한 다음 — 일반적으로 [0,1] 범위에서 — 원하는 범위의 크기를 곱하고 내림하는 구현에서도 발생한다. 여기에서 문제는 아무리 신중하게 생성하더라도 임의의 부동 소수점 숫자는 항상 유한한 정밀도만을 갖는다는 것이다. 즉, 주어진 범위 내에서 가능한 부동 소수점 값의 수가 유한하며, 범위를 이 숫자로 균등하게 나누지 않는 여러 세그먼트로 나누면 일부 세그먼트에 다른 세그먼트보다 더 많은 가능한 값이 생깁니다. 결과적인 바이어스는 체계적인 하향 추세를 보이지 않지만 여전히 존재한다.

== 의사 난수 생성기 (Pseudorandom generators) ==

피셔-예이츠 셔플을 의사 난수 생성기(PRNG)와 함께 사용할 때 몇 가지 문제가 발생할 수 있다. 생성기에 의해 출력되는 숫자 시퀀스는 시작 시점의 내부 상태에 의해 결정되므로, 생성기가 가질 수 있는 고유한 상태보다 더 많은 고유 순열을 생성할 수 없다.<sup>[23]</sup> PRNG의 상태 수는 순열 수보다 적어도 여러 자릿수 더 커야 편향을 최소화할 수 있다.

예를 들어, 많은 프로그래밍 언어 및 라이브러리의 내장 의사 난수 생성기는 32비트 내부 상태를 가지며, 이는 2<sup>32</sup>개의 서로 다른 숫자 시퀀스만 생성할 수 있음을 의미한다. 이러한 생성기로 52장의 트럼프 카드 덱을 셔플하면, 가능한 52! ≈ 2<sup>225.6</sup>개의 순열 중 극히 일부만 생성할 수 있다.<sup>[24]</sup> 226비트 미만의 내부 상태를 가진 생성기는 52장의 카드 덱의 가능한 모든 순열을 생성할 수 없다.

어떤 의사 난수 생성기도 초기화할 수 있는 고유한 시드 값보다 더 많은 고유 시퀀스를 생성할 수 없다.<sup>[25]</sup> 1024비트 내부 상태를 가진 생성기라도 32비트 시드로 초기화되면 초기화 직후 2<sup>32</sup>개의 서로 다른 순열만 생성할 수 있다. 초기화와 순열 생성 사이에 생성기를 여러 번 사용하면 더 많은 순열을 생성할 수 있지만, 이는 무작위성을 증가시키는 매우 비효율적인 방법이다.

선형 합동 PRNG를 사용하고 범위 축소에 나누기-나머지 방법을 사용할 때 추가적인 문제가 발생한다. 모듈로 2<sup>''e''</sup>를 갖는 선형 합동 PRNG의 하위 비트는 상위 비트보다 무작위성이 떨어진다.<sup>[6]</sup> 제수가 2의 거듭제곱일 때 나머지를 구하는 것은 상위 비트를 버리는 것을 의미하여 무작위성이 낮은 값을 얻게 된다. 이는 품질이 낮은 RNG 또는 PRNG가 품질이 낮은 셔플을 생성한다는 일반적인 규칙의 한 예이다.

8. 1. 구현 오류

8. 2. 모듈로 편향 (Modulo bias)

8. 3. 의사 난수 생성기 (Pseudorandom generators)

참조

<sub>[1]</sub> 간행물 Fisher–Yates shuffle https://www.isa-afp.[...] 2016
<sub>[2]</sub> 웹사이트 Let's Do the Knuth Shuffle https://golangprojec[...] 2023-04-02
<sub>[3]</sub> 서적 Statistical tables for biological, agricultural and medical research Oliver & Boyd
<sub>[4]</sub> 간행물 Algorithm 235: Random permutation https://dl.acm.org/d[...] 1964-07
<sub>[5]</sub> 서적 Seminumerical algorithms Addison–Wesley
<sub>[6]</sub> 서적 Seminumerical algorithms Addison–Wesley
<sub>[7]</sub> 웹사이트 Fisher–Yates shuffle https://xlinux.nist.[...] National Institute of Standards and Technology 2005-12-19
<sub>[8]</sub> 간행물 Uninitialized Reads: Understanding the proposed revisions to the C language https://cacm.acm.org[...] 2017-04-01
<sub>[9]</sub> 간행물 An algorithm to generate a random cyclic permutation 1986-05-30
<sub>[10]</sub> 학회자료 Overview of Sattolo's Algorithm http://algo.inria.fr[...] 2004-06-21
<sub>[11]</sub> 서적 Proceedings of the second annual ACM symposium on Parallel algorithms and architectures - SPAA '90 1990
<sub>[12]</sub> 논문 MERGESHUFFLE: A Very Fast, Parallel Random Permutation Algorithm 2015
<sub>[13]</sub> 웹사이트 The Danger of Naïveté https://blog.codingh[...] 2007-12-07
<sub>[14]</sub> 웹사이트 Provably perfect shuffle algorithms http://okmij.org/ftp[...] 2001-09-03
<sub>[15]</sub> 웹사이트 A simple shuffle that proved not so simple after all http://szeryf.wordpr[...] 2007-06-19
<sub>[16]</sub> 웹사이트 Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot http://www.robweir.c[...] 2010-02-27
<sub>[17]</sub> 웹사이트 Writing a sort comparison function, redux https://devblogs.mic[...] 2009-05-08
<sub>[18]</sub> 웹사이트 The GNU C Library: ISO Random https://www.gnu.org/[...]
<sub>[19]</sub> 웹사이트 Uniformity of random numbers taken modulo N https://stackoverflo[...]
<sub>[20]</sub> 웹사이트 Efficiently Generating a Number in a Range https://www.pcg-rand[...] 2018-07-22
<sub>[21]</sub> 서적 C Programming FAQs: Frequently Asked Questions https://c-faq.com/li[...] Addison-Wesley 1995
<sub>[22]</sub> 간행물 Fast Random Integer Generation in an Interval 2019-02-23
<sub>[23]</sub> 서적 Generating Random Permutations (PhD Thesis) https://maths-people[...] Australian National University 2009
<sub>[24]</sub> 웹사이트 How can I shuffle the contents of an array? https://benpfaff.org[...]
<sub>[25]</sub> 웹사이트 Random Number Generator Recommendations for Applications - Shuffling https://peteroupc.gi[...]
<sub>[26]</sub> 서적 Statistical tables for biological, agricultural and medical research Oliver & Boyd
<sub>[27]</sub> 간행물 Algorithm 235: Random permutation 1964-07
<sub>[28]</sub> 서적 Seminumerical algorithms Addison-Wesley
<sub>[29]</sub> 서적 Seminumerical algorithms Addison-Wesley
<sub>[30]</sub> 웹사이트 Fisher-Yates shuffle http://www.nist.gov/[...] National Institute of Standards and Technology 2005-12-19
<sub>[31]</sub> 학회자료 Overview of Sattolo's Algorithm http://algo.inria.fr[...] 2004-06-21
<sub>[32]</sub> 웹사이트 Provably perfect shuffle algorithms http://okmij.org/ftp[...] 2001-09-03
<sub>[33]</sub> 웹사이트 A simple shuffle that proved not so simple after all https://szeryf.wordp[...] 2007-06-19
<sub>[34]</sub> 웹사이트 Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot http://www.robweir.c[...] 2010-02-27
<sub>[35]</sub> 웹사이트 MS、Webブラウザ選択画面にアルゴリズム上のバグか https://atmarkit.itm[...] 2010-03-01
<sub>[36]</sub> 웹사이트 Writing a sort comparison function, redux http://blogs.msdn.co[...] 2009-05-08
<sub>[37]</sub> 웹사이트 The Danger of Naïveté http://www.codinghor[...] 2007-12-07
<sub>[38]</sub> 서적 Statistical tables for biological, agricultural and medical research https://archive.org/[...]
<sub>[39]</sub> 문서 최신 버전의 알고리즘은 효율적이어서 섞는 항목 수에 비례하여 시간이 걸리고 [[제자리 알고리즘|제자리에서]] 섞는다.
<sub>[40]</sub> 저널 Algorithm 235: Random permutation 1964-07
<sub>[41]</sub> 서적 Seminumerical algorithms
<sub>[42]</sub> 서적 Seminumerical algorithms
<sub>[43]</sub> 웹인용 Fisher–Yates shuffle https://xlinux.nist.[...] National Institute of Standards and Technology 2005-12-19
<sub>[44]</sub> 저널 An algorithm to generate a random cyclic permutation 1986-05-30