[Algorithm] 셔플 (Shuffle)

1. 셔플(Shuffle)이란?
셔플은 카드게임에서 카드를 섞는 것이다. 카드들의 자리를 서로 바꿔가며 섞는다는 것은 어찌보면 간단하지만, 반드시 주의해야 할 점이 있다. 과연 셔플이 모든 카드를 공평하게 섞느냐(Uniformly Random)에 관한 것이다.
먼저, 셔플의 구현 과정에서 흔히 실수할 수 있는 부분을 살펴본 뒤에, 제대로된 셔플을 구현해보도록 하겠다.

2. 셔플(Shuffle)의 구현
셔플은 배열에서 원소들의 자리를 임의적으로(Randomly) 바꾸어가며 섞는 경우와 동일하게 생각할 수 있다. 배열에 할당된 각각의 공간들이 카드가 놓일 자리라는 관점으로 접근을 해보자. 어떤 식으로 구현을 해야 할까?
우선 첫 번째로는, 간단하게 각각의 카드에 일정 숫자를 랜덤으로 부여하고, 그 숫자를 기준으로 정렬(Sort)을 하는 방법을 떠올릴 수 있다.

하지만, 이 경우에는 따로 정렬을 해야 한다는 부담이 있다. 어떤 정렬 알고리즘을 쓰냐에 따라 시간복잡도가 결정되며, 현재 이론적으로 모든 정렬 알고리즘은 O(NlogN)보다 효율적일 수 없다고 알려져 있다. 이보다 더욱 효율적인 알고리즘은 없을까?

그렇다면 두 번 째 방법으로, 배열의 원소들 중 맨 첫 번 째부터 진행하면서, 배열 내의 아무 원소나 하나 뽑아서 현재 진행 중인 원소(Current)와 바꿔치기하는 방법을 떠올릴 수 있다. 이렇게 하면 마지막 원소의 차례가 되었을 때, 카드들이 뒤죽박죽 섞여있게 될 것이다. 아주 쉽고 간단한 방법이다.

그런데, 과연 이 셔플 방법이 모든 원소를 공평하게 섞었을까? 사실 이 방법은 공평하지 않다. 이 방법을 현금이 걸려있는 사행성 카드게임의 셔플 알고리즘으로 사용한다면, 엄청난 문제를 야기할 수 있다.

그렇다면 왜 공평하지 않은지 차근차근 살펴보자. 위의 알고리즘은 다음과 같이 비유할 수 있다.

1부터 N까지 번호가 매겨져 있는 카드 N장이 있고, 바닥에는 1부터 N까지 번호가 매겨져 있는 상자가 N개 있다고 가정하자. 첫 번째 상자부터 시작해서, N 번째 상자까지 하나씩 이동하면서, 각각의 상자에 들어갈 카드가 무엇인지 확정하려고 한다.

우선 처음에는 카드를 아무렇게나 한 장씩 각각의 상자에 넣은 다음, 1 ~ N의 숫자 중 하나를 마음대로 골라서 그 숫자를 가지고 있는 카드를 찾아 현재 상자에 들어있는 카드와 자리를 바꾼다.

이때, 상자 하나에는 확률적으로 N장의 카드가 올 수 있으므로, N개의 상자에 카드가 놓일 수 있는 경우의 수는 N의 N제곱(N^N)이라고 할 수 있다.

그런데, 실제 이론적으로는 카드가 놓일 수 있는 경우가 N장의 카드 중 N개를 선택해서 나열하는 방법, 즉, 순열의 개념이므로 실제 전체 경우의 수는 NPN=N!이다.

그런데, N^N은 N!보다 훨씬 큰 숫자이기 떄문에, 특정 순열이 다른 순열들 보다 몇 차례 더 발생한다는 것을 알 수 있다.

카드 3장을 가지고 직접 해보자. 1, 2, 3 세 장의 카드의 자리를 바꾸어가며 진행하면, 1 3 2 와 2 1 3 그리고 2 3 1이 다른 순열보다 한 번 씩 더 나타난다는 것을 알 수 있다. 즉, 이 세 개의 순열들이 다른 순열들보다 확률적으로 더 나오기 쉽다는 뜻이다.

다시 말해서, 이 방법은 공평하게 카드를 섞는 방법이 아닌 것이다. 그렇다면, 어떻게 공평하게 섞을 수 있는가를 고민해 봐야한다. 이론상  NPN=N! 개의 순열을 공평하게 발생시켜야 한다는 것에 초점을 맞추면 된다.

카드가 놓일 상자에 어떤 카드를 놓을지 선택할 때, 전체 N장의 카드를 후보로 설정하지 않고, 아직 놓이지 않은 카드들을 후보로 설정하면 된다.

그러면 모든 가능한 경우의 순열들(NPN=N! 개의 순열)을 각각 균등하게 얻을 수 있게 된다.

이러한 알고리즘은 Knuth Shuffle또는 Fisher-Yates Shuffle이라고 불리기도 한다.

3. 셔플(Shuffle)의 수학적 분석

앞서 언급했듯이, 정렬 알고리즘은 적어도 O(NlogN)의 시간복잡도를 갖게 된다. 그렇다면, 앞서 구현한 셔플은 어떠한 시간복잡도를 가질지 생각해보자.

시간복잡도 계산에 있어서 Cost Model을 배열에의 접근(Array Access)으로 설정합시다.

그러면, 반복문을 통해 배열의 첫 번 째 원소(index 0)부터 끝(index N-1)까지 이동하며 수행하므로 일단 N번의 연산수행이 기본적으로 일어납니다.

그리고, 한 번 수행할 때마다 랜덤으로 배열 내의 다른 원소를 뽑아서 현재 원소(Current)와 서로 자리를 바꾸게 되는데, 이 과정은 N의 증감에 관계 없이 일정하므로 상수(Constant)의 수행 횟수를 가지게 된다. 즉, 셔플 알고리즘은 O(cN = N)에 비례한 시간복잡도를 갖게 된다.

4. Source Code

https://github.com/arkainoh/algorithms/blob/master/c/Shuffle.c

void swap(int* arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}
void Shuffle(int* arr, int from, int to) {
  for(int i = to; i > from; i--) {
    int r = rand() % (i + 1);
    swap(arr, r, i);
  }
}

5. References

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Robert Sedgewick's Algorithms Part I, Princeton University