Shuffle Algorithm - Fisher-Yates
대표적인 Shuffle(썩기) 알고리즘인 Fisher-Yates 알고리즘에 대해서 알아보자.
Python의 random 모듈에 구현되어 있기 때문에 굳이 별도의 함수로 구현할 필요없아 가져다 쓰기만 하면된다.
from random import shuffle
a = [x for x in range(100)]
b = shuffle(a)
print(b)
CPython에 구현된 shuffle() 함수가 현대적인 Fisher-Yates 알고리즘의 구현이다.
Python으로 굳이구현해 보자면 아래와 같다.
from math import floor
from random import random
def shuffle(x):
for i in reversed(range(1, len(x))):
j = floor(random() * (i + 1))
x[i], x[j] = x[j], x[i]
return x
0에서 99까지의 리스트를 썩어보자.
a = [x for x in range(100)]
b = shuffle(a)
print(b)
[68, 10, 73, 26, 67, 20, 43, 58, 6, 33, 27, 11, 59, 91, 65, 84, 51, 53, 87, 39, 93, 72, 85, 34, 78, 30, 63, 15, 82, 48, 98, 86, 16, 89, 95, 83, 47, 77, 24, 25, 40, 61, 69, 64, 22, 17, 29, 5, 3, 4, 74, 92, 42, 57, 88, 13, 23, 31, 94, 12, 8, 0, 35, 81, 28, 52, 45, 9, 49, 79, 90, 50, 76, 75, 66, 18, 46, 38, 14, 2, 96, 32, 99, 55, 36, 7, 44, 60, 21, 54, 1, 37, 41, 97, 19, 71, 56, 70, 62, 80]
CPython에 구현된 shuffle() 함수를 참고 하였다.
확률 계산
$n$개의 슬롯을 가지는 배열을 가정하자
배열의 첫 번째 요소가 $n$ 번째 슬롯에 위치할 확률을 계산해 본다.
- $n$ 번째 슬롯는 첫 번째 iteration에서 요소가 결정 되기 때문에 확률은 $\frac{1}{n}$ 이 된다.
같은 방법으로 배열의 첫 번째 요소가 $n-1$ 번째 슬롯에 위치할 확률을 계산해 보자. 다음 확률의 곱과 같다.
- 첫 번째 요소가 $n$ 번째 슬롯에 위치하지 않을 확률: $\frac{n-1}{n}$
- 첫 번째 요소가 $n-1$ 번째 슬롯에 위치할 확률: $\frac{1}{n-1}$
$$\frac{n-1}{n} \times \frac{1}{n-1} = \frac{1}{n}$$
마찬가지로 배열의 첫 번째 요소가 $n-2$ 번째 슬롯에 위치할 확률은 아래 확률의 곱과 같다.
- 첫 번째 요소가 $n$ 번째 슬롯에 위치하지 않을 확률: $\frac{n - 1}{n}$
- 첫 번째 요소가 $n-1$ 번째 슬롯에 위치하지 않을 확률: $\frac{n-2}{n-1}$
- 첫 번째 요소가 $n-1$ 번째 슬롯에 위치할 확률: $\frac{1}{n-2}$
$$\frac{n - 1}{n} \times \frac{n-2}{n-1} \times \frac{1}{n-2} = \frac{1}{n}$$
위와 같이 모든 요소에 대하여 첫 번째 슬롯에 위치할 확률을 구해보면 모두 $\frac{1}{n}$ 인 것을 알 수 있다.
같은 방법으로 임이의 $x$ 번째 요소($0 \le x \le n-1$)가 임이의 슬롯 $s$ ($0 \le s \le n-1$)에 위치할 확률을 구해보면 모두 $\frac{1}{n}$ 인 것을 알 수 있다.
제비뽑기순서에 따른 당첨 확률 문제과 같다.
SWAP 구조이기 때문에 구조적으로 사다리티기와 비슷한 구조다. 사다리타기에서 사다리의 디딤대의 형태가
random함수가 되는 것이다.
검증
만든 프로그램을 검증 해보자.
elements = 10
times = 1000000
# 빈도수를 저장하기 위한 변수를 초기화 한다.
freqs = [[0 for x in range(elements)] for x in range(elements)]
# times 번 반복하면서
for n in range(times):
# elements개의 요소를 가지는 리스트르 만든다.
values = list(range(elements))
# 리스트를 썩은 다음
for i, x in enumerate(shuffle(values)):
# 빈도수를 기록한다.
freqs[i][x] += 1
# 이쁘게 출력 하자
print(" |", end="")
for x in range(elements):
print(f'{x:7} |', end="")
print("")
print("-"*99)
for i, freq in enumerate(freqs):
print(f" slot {i} |", end="")
for x in freq:
print(f'{x:7} |', end="")
print("")
결과는 다음과 같다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---------------------------------------------------------------------------------------------------
slot 0 | 100024 | 100224 | 99795 | 99715 | 99240 | 100132 | 99944 | 99976 | 101189 | 99761 |
slot 1 | 100363 | 100020 | 99848 | 100309 | 99758 | 99989 | 100217 | 99855 | 99750 | 99891 |
slot 2 | 99745 | 100285 | 99743 | 100022 | 99959 | 100102 | 100179 | 100006 | 100182 | 99777 |
slot 3 | 100094 | 100119 | 99648 | 100087 | 99581 | 100774 | 100027 | 100250 | 99891 | 99529 |
slot 4 | 100572 | 100177 | 100148 | 99262 | 99783 | 99912 | 99750 | 100074 | 99780 | 100542 |
slot 5 | 99870 | 99904 | 100456 | 100140 | 100646 | 99648 | 99582 | 99584 | 100136 | 100034 |
slot 6 | 100250 | 99615 | 99958 | 99859 | 100889 | 99716 | 100071 | 99947 | 99687 | 100008 |
slot 7 | 99396 | 100119 | 100087 | 100373 | 100388 | 99841 | 99873 | 100080 | 99679 | 100164 |
slot 8 | 99694 | 99856 | 100316 | 100036 | 100028 | 99627 | 99903 | 100097 | 100238 | 100205 |
slot 9 | 99992 | 99681 | 100001 | 100197 | 99728 | 100259 | 100454 | 100131 | 99468 | 100089 |
- 10개의 요소를 가지를 리스트를 섞었으니 첫 번째 슬롯에 1이 나올 확률은 실행 휫수의 $\frac{1}{10}$ 이다.
1000000번 시도하였으니 기대값은 $\frac{1}{10}$ 인100000이지만24많은100024이 나왔다.- 결과값이 대체적으로
100000언저리에서 놀고 있으니 잘 동작 한다고 보도록 하자.
