-
Fisher-Yates ShuffleDiscrete 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