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() 함수를 참고 하였다.

확률 계산

  1. $n$개의 슬롯을 가지는 배열을 가정하자

  2. 배열의 첫 번째 요소가 $n$ 번째 슬롯에 위치할 확률을 계산해 본다.

    • $n$ 번째 슬롯는 첫 번째 iteration에서 요소가 결정 되기 때문에 확률은 $\frac{1}{n}$ 이 된다.
  3. 같은 방법으로 배열의 첫 번째 요소가 $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}$$

  4. 마찬가지로 배열의 첫 번째 요소가 $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}$$

  5. 위와 같이 모든 요소에 대하여 첫 번째 슬롯에 위치할 확률을 구해보면 모두 $\frac{1}{n}$ 인 것을 알 수 있다.

  6. 같은 방법으로 임이의 $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 언저리에서 놀고 있으니 잘 동작 한다고 보도록 하자.