우리는 종종 무언가를 잘 뒤섞을 필요가 있습니다. 예를 들어, 친구들과 여행을 가서 저녁을 맛있게 먹은 다음 설거지 당번을 뽑는 경우를 생각해 봅시다. 다양한 방법이 있겠지만, 가장 고전적인 방법 중 하나는 종이 조각을 사람 수만큼 준비하고 한 곳에 '꽝'을 적은 후 이를 잘 뒤섞고 한 명씩 종이 조각을 뽑는 것입니다. 이때 우리는 이 조각들이 잘 뒤섞여 있기를 바랍니다. 다른 예시로는 포커 게임을 들 수 있겠습니다. 딜러는 게임을 시작하기 전에 카드를 뒤섞습니다. 이때 게임 참가자들은 카드가 잘 뒤섞여 있기를 희망할 터입니다. 그렇다면, 과연 어떻게 하면 잘 뒤섞을 수 있을까요?
사실 이 주제는 처음부터 제가 정리하겠다고 염두에 둔 주제는 아니었습니다. 처음에는 쿠폰 수집가 문제(coupon collector problem)와 커플링 기법(coupling method)을 활용하여 (거의) 균등한 확률로 순열(permutation) 하나를 출력하는 방법에 관해 정리하던 중이었습니다. 그러다 문득 랜덤 순열(random permutation)을 얻는 다른 방법이 있는지 궁금해졌고, 인터넷에 검색해 보니 피셔-예이츠 셔플(Fisher-Yates shuffle)이 가장 먼저 등장하더군요. 찬찬히 읽어 보니 간단하지만 효율적인 알고리즘이더군요. 그래서 빠르게 정리해 보기로 결정했습니다.
순열은 1부터 \(n\)까지 순서를 고려하여 일렬로 나열한 것을 의미합니다. 즉 어떤 순열 \( \pi : \{1, \cdots, n\} \to \{1, \cdots, n\} \)은 반드시 \[ \{\pi(1), \cdots \pi(n)\} = \{1, \cdots, n\} \]을 만족합니다. 모든 순열을 모아 놓은 집합을 \(\Pi\)라고 부르겠습니다. \( |\Pi| = n! \)이 된다는 것은 잘 알려진 사실입니다. 우리의 목표는 균등한 확률로 순열 하나를 뽑는 것입니다. 엄밀히 말하자면, 임의의 순열 \( \pi \in \Pi \)에 대해, \[ Pr[ \pi \text{ is selected} ] = \frac{1}{n!} \]이 되도록 순열을 뽑아야 합니다.
가장 간단한 방법은 1부터 \(n!\) 사이의 숫자 중에 하나를 균등한 확률로 고르고 \(\Pi\)에서 해당 숫자 번째에 위치한 순열을 선택하는 것입니다. 하지만 이 방법은 매우 멍청하다는 사실을 쉽게 눈치채셨으리라 생각합니다. 바로 \(n!\)이 너무 크기 때문인데요. 1부터 \(n!\) 사이의 수를 (이조차도 쉽지는 않지만 어떻게든) 하나 골랐다고 합시다. 해당 숫자 번째에 위치한 순열을 얻기 위해서는 \(\Pi\)의 모든 순열이 저장되어 있거나 \(\Pi\)의 순열을 하나씩 순회해야 하는데요. 전자는 너무 많은 공간을 필요로 하고, 후자는 너무 많은 시간을 요합니다. 따라서 이보다 훨씬 효율적인 방법을 고민해야 합니다.
사실 앞에서 소개한 간단한 방법이 가장 직관적인 방법은 아니라고 생각합니다. 오히려 다음의 방법이 보다 직관적으로 다가올 터입니다.
- 1부터 \(n\)까지를 일단 일렬로 나열한다. 이를 \(S\)라고 부른다.
- 아무것도 담지 않은 \(R\)을 만든다.
- 1부터 \(n\)까지 중 숫자 하나를 균등한 확률로 선택한다. 이를 \(j\)라고 한다.
- \(S\)의 \(j\) 번째 수를 \(R\)에 덧붙이고, \(S\)에서 제거한다.
- 1부터 \(n - 1\)까지 중 숫자 하나를 균등한 확률로 선택한다. 이를 \(j\)라고 한다.
- \(S\)의 \(j\) 번째 수를 \(R\)에 덧붙이고, \(S\)에서 제거한다.
- \(\cdots\)
요약하면, 매번 균등한 확률로 \(S\)에서 숫자 하나를 선택해 \(R\)에 계속 덧붙이는 방법입니다. 아주 그럴싸합니다. 그리고 놀랍게도 이 방법이 곧 피셔-예이츠 셔플입니다. 아래는 굳이 알고리즘처럼 기술한 것입니다.
알고리즘 1. 피셔-예이츠 셔플 (Fisher-Yates shuffle)
입력: 수열 \(1, \cdots, n\)
출력: 랜덤 순열
- \(S \gets \{ 1, \cdots, n \} \) (단, 순서가 존재한다.)
- 길이가 \(n\)인 배열 \(R\)을 만든다.
- \(i \gets n, n-1, \cdots, 1\)에 대해서 다음을 수행한다.
- 1에서 \(i\)까지 숫자 중 균등한 확률로 숫자 \(j\)를 하나 선택한다.
- \(S\)의 \(j\) 번째 원소를 \(x\)라고 하자. \(S \gets S \setminus \{x\} \)
- \(R[i] \gets x\)
- \(R\)을 출력한다.
증명을 해야 하나 싶을 정도로 직관적인 알고리즘입니다만, 굳이 증명을 밝혀 적어 보겠습니다.
정리 1. 알고리즘 1의 정확성
임의의 순열 \( \pi \in \Pi\)에 대해, \( Pr[R = \pi] = \frac{1}{n!} \)을 만족한다.
[증명] \(R = \pi\)가 되려면, 매 \(i = n, \cdots, 1\)에 대해, \(R[i] = \pi[i]\)를 만족해야 합니다. 위 알고리즘은 한 번 \(R[i]\)를 \(S\)로부터 뽑아서 고정한 다음에는 수정하지 않습니다. 따라서 매 단계 \(i = n, \cdots, 1\)마다 \(S\)로부터 \(\pi[i]\)에 해당하는 숫자를 뽑았어야 합니다. 간단한 귀납법으로 매번 \(S\)에 \(\pi[i]\)가 존재함을 보일 수 있습니다. 게다가 그때 \(\pi[i]\)가 뽑힐 확률은 균등하므로 \( \frac{1}{i} \)과 같습니다. 이를 모두 엮으면 정리의 명제를 쉽게 보일 수 있습니다. ■
이제 알고리즘 1이 올바르게 동작한다는 것은 알게 되었습니다. 그렇다면 수행 시간은 어떻게 될까요? 단계 1, 2는 \(O(n)\) 시간에 가능합니다. 단계 3은 총 \(n\) 번 수행됩니다. 단계 3-a는 자세히 다루지는 않겠지만 상수 시간에 해결될 것으로 기대할 수 있습니다.[ㄱ] 단계 3-c도 상수 시간에 수행될 수 있습니다. 하지만 단계 3-b는 자칫 잘못하면 매번 \(S\)를 구현하는 자료 구조를 한 번씩 순회해야 할 수도 있습니다. 즉, \(O(n)\) 시간이 걸린다는 것이죠. 따라서 멍청하게 구현하면 총 \(O(n^2)\) 시간에 동작합니다.
더 빠르게 동작하도록 만들 수 있을까요? \(O(n^2)\)의 수행 시간을 만든 원흉은 바로 단계 3-b였습니다. 해당 단계를 상수 시간에 해결할 수 있으면 우리는 총 \(O(n)\) 시간에 동작하는 알고리즘을 만들 수 있을 것입니다.
\(S\)의 \(j\) 번째 원소를 뽑을 때 사실 \(S\)의 원소들의 순서는 고정되어 있을 필요가 없습니다. 정리 1의 증명에서 결국 우리가 필요한 것은 \(S\)의 각 원소를 균등한 확률로 뽑는 것이었습니다. 이를 위해 굳이 \(j\)를 두어 1부터 그때 \(S\)의 길이인 \(i\)까지 중에 정수 하나를 균등한 확률로 선정했습니다. 하지만 \(j\)가 균등한 확률로 선정되므로 \(S\)의 원소들은 어느 순서로 나열되어 있든지 간에 각 원소가 뽑힐 확률도 여전히 균등합니다. 이 성질은 이전 단계의 \(S\)와 이후 단계의 \(S\)의 순서도 서로 연관될 필요가 없다는 결론도 도출합니다.
다음과 같은 알고리즘을 생각해 보겠습니다.
알고리즘 2. 피셔-예이츠 셔플 (선형 수행 시간)
입력: 수열 \(1, \cdots, n\)
출력: 랜덤 순열
- 길이가 \(n\)인 배열 \(A\)를 만든다.
- \( A[i] \gets i \)
- \(i \gets n, n-1, \cdots, 1\)에 대해서 다음을 수행한다.
- 1에서 \(i\)까지 숫자 중 균등한 확률로 숫자 \(j\)를 하나 선택한다.
- \(A[j]\)와 \(A[i]\)의 값을 서로 바꾼다.
- \(A\)를 출력한다.
알고리즘 2에서 뽑히는 숫자가 알고리즘 1에서의 \(x\)와 동일하도록 만드는 (아주 간단한) 커플링 기법을 사용하면 매 단계 \(i = n, n-1, \cdots, 1, 0\)에 대해서, 다음 두 가지를 항상 만족함을 쉽게 보일 수 있습니다. 이때 \(i = 0\)은 단계 3을 탈출한 때를 의미합니다.
- \(A[1:i]\)의 숫자들은 곧 알고리즘 1의 \(S\)의 원소와 동일하다.
- \(A[i+1:n] = R[i + 1, n]\)
따라서 최종적으로는 \(A = R\)이 되어 알고리즘 2가 출력하는 \(A\)도 올바른 랜덤 순열이 됩니다. (증명을 적고 나서 보니 굳이 커플링 기법을 사용하여 증명할 필요도 없어 보입니다. 정리 1과 유사한 방법으로도 증명할 수 있겠습니다.)
수행 시간을 따져 볼까요? 이 알고리즘에서는 단계 3-b가 상수 시간에 동작한다는 것을 쉽게 알 수 있습니다. 따라서 이 알고리즘은 우리가 처음에 기대한 대로 \(O(n)\) 시간에 동작합니다.
참고
[1] Fisher-Yates shuffle. Wikipedia. Link: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
주석
[ㄱ] 제가 아는 한 현재의 컴퓨터로는 완벽한 랜덤성(randomness)을 구현할 수 없습니다. (반면, 양자 컴퓨터에서는 가능합니다.) 하지만 컴퓨터과학 이론에서는 랜덤 알고리즘의 성능을 분석하기 위해서 공정한 동전(fair coin)을 한 번 던져서 앞면이 나오면 0, 뒷면이 나오면 1의 값을 갖는 랜덤 비트(random bit)가 있다고 가정합니다.
본문에서는 편의 상 1부터 \(i\)까지 중의 정수를 고르는 것으로 하였지만, 이번에는 0부터 \(i\)까지 중의 정수를 하나 고르겠습니다. 만약 \(i\)가 \(2^k - 1\)의 꼴로 표현될 수 있다면, 랜덤 비트 \(k\)개를 통해 그 사이의 정수 하나를 균등한 확률로 선정할 수 있습니다.
문제는 \( 2^{k - 1} - 1 < i < 2^k - 1 \)의 상황입니다. 이때는 \(k\) 개의 랜덤 비트로 나온 값이 0에서 \(i\) 사이에 들어오지 않으면 그 사이에 들어올 때까지 계속 수행하는 것으로 균등한 확률로 정수 하나를 선정할 수 있습니다. 균등한 확률로 정수 하나가 선택된다는 것은 자명해 보이지만, 운이 나쁘면 이 작업을 계속해야 한다는 문제가 있습니다. 하지만 \(i\) 값이 \(2^{k-1}\)보다 크거나 같기 때문에 \(k\) 개의 랜덤 비트로 나온 값이 \(i\)보다 커져서 작업을 다시 수행하는 확률은 \(\frac{1}{2}\)보다 작습니다. 따라서 두 번의 수행으로 0에서 \(i\) 사이의 값을 하나 얻을 것을 기대할 수 있습니다.