A SAMPLE PROBLEM

Jon Bentley가 쓴 Programming Pearls 12장. SAMPLE PROBLEM을 정리한 글이다.

문제

여론 조사 기관에서는 N 명의 사람 중에서 M 명의 사람을 무작위로 추출하여 설문 조사를 한다.

M < N

N 명의 사람엔 0부터 시작하는 일련번호가 부여되어 있다. N을 5라고 가정하면 다음과 같다.

0 강백호
1 서태웅
2 채치수
3 정대만
4 송태섭

M이 2라면 이 중 동일한 확률로 2명을 추출해야 한다.

이는 0에서 N 사이에서 M 개의 숫자를 동일한 확률로 무작위로 추출하는 것에 다름아니다.

* 이 문제를 해결하는데 다음 2 함수를 사용할 수 있다.

bigrand : m 혹은 n 보다도 클 수 있는 정수를 무작위로 반환한다.
randint(i, j) : i에서 j 사이에 포함되어 있는 정수를 무작위로 반환한다.


솔루션 1

select = m
remaining = n
for i = [0, n)
  if (bigrand() % remaining) < select
    print i
    select--
  remaining--

* 추출된 숫자는 m 보다 많을 수도 m 보다 적을 수도 없다. 강조한 부분을 주의 깊게 보면 이를 파악할 수 있다.

일련번호가 0인 강백호가 선택될 확률은 2 / 5이지만 이 후에 있는 사람들이 선택될 확률은 앞 결과에 영향을 받는다. 예를 들어 강백호가 선택되면 일련번호가 1인 서태웅이 선택될 확률은 1 / 4이고, 강백호가 선택되지 않으면 서태웅이 선택될 확률은 2 / 4이다.

그러나 전체적으로는 서태웅이 추출될 확률도 2 / 5이다.

서태웅이 추출될 확률
= 강백호가 추출될 확률 (2 / 5) * 1 / 4 + 강백호가 추출되지 않을 확률 (3 / 5) * 2 / 4
= 2 / 20 + 6 / 20
= 2 / 5

이를 C++로 구현하면 다음과 같다.

void genknuth(int m, int n)
{
  for (int i = 0; i < n; i++)
    if ((bigrand() % (n - i) < m) {
      cout << i << "\n";
      m--:
    }
}

솔루션 2

set에 난수를 담는 방법도 있다.

* set에는 동일한 값이 들어 갈 수 없다.

initialize set S to empty
size = 0
while size < m do
  t = bigrand() % n
  if t is not in S
    insert t into S
    size++
print the elements of  S in sorted order

C++ STL을 이용하여 구현하면 다음과 같다.

void gensets(int m, int n)
{
  set<int> S;
  while (S.size() < m)
    S.insert(bigrand() % n);
  set<int>::iterator i;
  for (i < S.begin(); i != S.end(); ++i)
    cout << *i << "\n";
}

솔루션 3

n 개 크기 배열을 만든 후에 이들의 위치를 무작위로 변경(swap)하고 처음 m 개를 선택하는 방법도 있다. 화투나 포카에서 카드를 섞는 것(shuffle)과 유사하다.

for i = [0, n)
  swap(i, randint(i, n - 1))

C++를 구현하면 다음과 같다.

void genshuf(int m, int n)
{
  int i, j;
  int *x = new int[n];
  for (i = 0;; i < n; i++)
    x[i] = i;
  for (i = 0; i < m; i++) {
    j = randint(i, n - 1);
    int t = x[i]; x[i] = x[j]; x[j] = t;
  }
  sort(x, x + m)
  for (i = 0; i < m; i++)
    cout << x[i] << "\n";
}

개념 코드와는 다르게 m개 까지만 swap한다. (Ashley Shepherd와 Alex Woronow)



기타

만약 n이 100만이고 m이 n - 10이라면 조금은 다르게 접근해야 한다. 이 경우에는 추출되지 않을 10개를 계산하는 것이 적합하다.

프로그래밍 혹은 문제 해결은 다음과 같이 진행된다.

1. Understand the Perceived Problem
2. Specify an Abstract Problem
3. Explore the Design Space
4. Implement One Solution
5. Retrospect