n人中m人が当選するくじ in C++ DouKaku?

n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。

C++で書いてみたらCしかなかた...

vector<int>
shuffle(int n, int m)
{
  vector<int> ret;
  if (n <= 0 || m <= 0 || n < m)
    return ret;

  vector<int> v(n);
  for (int i = 0; i < n; i++)
    v[i] = i + 1;

  int cnt = 0;
  ret.resize(m);
  while (cnt < m) {
    int idx = rand() % v.size();
    int val = v[idx];
    v.erase(v.begin() + idx);
    ret[cnt++] = val;
  }

  sort(ret.begin(), ret.end());
  return ret;
}

yuさん/elm200さんのやり方の拡張です。

解説。
まずソーティングの代わりに選択アルゴリズムを使うことで
計算量が線形になります。

また、配列の各要素にランダム値を付加し、
その大小に基づいてソートする方法 (sort_by) だと
厳密には公平になりません。

例えば、2人から1人を選ぶとき
各々に割り振ったランダム値 (r[x] とします) 
r[0] < r[1] となる確率と r[0] > r[1] となる確率は等確率となりますが
わずかに r[0] == r[1] となることがあり、
その場合、例えば先頭からm個とると必ず先の人が選ばれることになるので、
前の人が若干有利になってしまいます。
これは、比較関数自体をランダムにすることで解決します。（多分）

#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

bool randcmp(const int n1, const int n2)
{ return rand() &1; }

vector<int> lot(int n, int m)
{
  vector<int> v(n);
  for (int i = 0; i < n; ++i) { v[i] = i+1; }
  const int t = (m <= n/2) ? m : n-m;
  vector<int>::iterator first = v.begin(), mid = v.begin()+t;
  nth_element(first, mid-1, v.end(), randcmp);
  if (t < m) { first = mid; mid = v.end(); }
  return vector<int>(first, mid);
}

DouKaku?

n人中m人が当選するくじ

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq