ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Fisher-Yates Shuffle
    Discrete mathmatics and Problem Solving/etc radom, samplings 2019. 11. 4. 17:52

    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이 있긴하다.

    'Discrete mathmatics and Problem Solving > etc radom, samplings' 카테고리의 다른 글

    Fisher-Yates Shuffle  (0) 2019.11.04

    댓글 0

Designed by Tistory.