Fisher-Yates Shuffle

FIsher-Yates Shuffle

순서를 정하는 문제에 직면하였을 때, 원소들을 어떻게 무작위적으로 배치하는가 생각이 들었다.

산업공학과 학부 시절에 가장 흥미가 있었던 분야가 통계/실험계획법이었기에, 랜덤/샘플링 이라는 단어만 들어도 그냥 재밌을것 같다.

현실 문제

만약 n 명의 사람이 있다. n 명의 사람을 일렬로 세우는데 순서를 무작위적으로 바꾸기 위한 알고리즘을 제시하라.

편향된 알고리즘 제시

이 이야기를 시작하기 전에 우선 편향된 알고리즘을 보여주려고 한다.
n 개의 원소를 무작위로 셔플하는 naive approach

#include <iostream>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <vector>

using namespace std;
vector<int> ans;
set<int> s;
int main()
{
    srand(time(0));
    int n;
    n = 10;
    while( ans.size()<10)
    {
        for (int i=1; i<=n; i++)
        {
            if ( rand()%2)
            {
                if ( s.find(i) == s.end()) 
                {
                    ans.push_back(i);
                    s.insert(i);
                }
            }
        }
    }

    for (int a : ans)
        cout << a << " ";
        cout <<"\n";
}

위 알고리즘 에서 첫번째 원소가 첫 번째로 뽑힐 확률은 1/2 보다 크다. 이것은 우리가 원하는 공평한 알고리즘은 아니다.

생각 step 1

각 각의 사람 i_1, i_2, i_3, ... i_n 은 위치 p_1, p_2, p_3, ... p_n 에 각각 1/n 확률로 위치해야한다.

첫 번째 사람을 1/n 확률로 뽑아보자.

j = pick(1, n+1);

pick(1, n+1)가 1부터 n까지 원소 중 uniform하게 한 원소를 선택한다고 가정하면, j는 1~n 중 한 인덱스를 1/n 확률로 선택된다. 그리고 집합에서 j 번째 원소를 제거한다. 이제 집합은 (n-1) 크기가 된다.

ans.add( a[j] );

생각 step 2

두 번째 사람을 뽑아보자. 집합에서 한 사람을 뽑자. 범위는 1 ~ n-1 이다. 그리고 이 사람을 정답 대기열에 추가한다.

j = pick(1, n);
ans.add( a[j] );

생각 증명

이 단계까지 왔을 때, 수행한 연산들을 되짚어보자. 임의의 원소가 첫번째가 될 원소로 뽑힐 확률은 1/n이다. 임의의 원소가 두번째 원소로 뽑을 확률은 (n-1)/n * 1/(n-1) = 1/n이다. 세 번째 원소로 뽑힐 확률은 (n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n 이다.

구현

확률적으로 공평하게 셔플하는 fihser-yates shuffling

#include <iostream>
#include <random>
#include <vector>
using namespace std;

vector<int> v, ans;
int main()
{
    int n = (int)2e7;
    for (int i=1; i<=n; i++)
        v.push_back(i);

    mt19937_64 eng(random_device{}());

    int m = n;
    for (int i=0; i<n; i++)
    {
        uniform_int_distribution<> dist(0, m-1);
        int j = dist(eng);
        ans.push_back(v[j]);
        v.erase(v.begin()+j, v.begin()+j+1);
        m--;
    }

    for (int i : ans)
        cout << i << " ";
    cout << "\n";
}

swap을 활용한 더 나은 수행복잡도.

#include <iostream>
#include <random>
#include <vector>
using namespace std;

vector<int> v, ans;
int main()
{
    int n = (int)2e5;
    for (int i=1; i<=n; i++)
        v.push_back(i);

    mt19937_64 eng(random_device{}());

    for (int i=n-1; i>0; i--)
    {
        uniform_int_distribution<> dist(0, i-1);

        int j = dist(eng);

        int tmp = v[j];
        v[ j ] = v[ i ];
        v[ i ]  = tmp;
    }

    for (int i : v)
        cout << i << " ";
    cout << "\n";
}

이 결과물에서 k 개만큼 절삭하거나, k 번만 추출하면 n 개의 결과물에서 k 개만 공평하게 뽑는 알고리즘이 된다. 

n 개의 결과물에서 k 개만 공평하게 뽑는 알고리즘 중에는 fisher-yates shuffling 말고도 resvoir sampling이 있긴하다.