nまでの整数からm個ランダムに選ぶ

testlib.h を使ったgenerator用のライブラリです。

vector<long long> select(n, m)

\{0, 1, ..., n-1\} から m 要素をランダムに取り出します。戻り値はソートされています。

vector<long long> grouping(n, m, min_size=0)

n 個を m グループにランダムに分けます。戻り値はグループサイズの配列です。

計算量はどちらも O(mlogm) です。

配列 v から m 要素ランダムに取り出す関数だけ必要なら、これを使わずに shuffle して先頭 m 要素取り出す方法でも良いと思います。
n が小さいときもこれでいけます。

アルゴリズム

grouping は select を使っています。なので、select についてのみ解説します。

select(n, m) は  n \geq 2m、すなわち半分以下しか select しない場合は、ランダムに選んでまだ選ばれていなかったら追加し、そうでなければまだ選ばれていないものが選ばれるまで再抽選し続けることを m 回繰り返します。少なくとも半分はまだ選ばれていないので、1回あたり抽選回数の期待値は2回以下となり、平均して O(m) が達成されます。

 n > 2m の場合、選ばないものを select(n, n-m) によって選びます。

// select S ⊆ {0, 1, ..., n-1} and |S| = m
std::vector<long long> select(long long n, int m) {
  assert(m <= n);
  if (m * 50 <= n) {
    std::set<long long> used;
    std::vector<long long> res(m);
    for (int i = 0; i < m; ++i) {
      long long x;
      do {
        x = rnd.next(n);
      } while (used.count(x) > 0);
      res[i] = x;
      used.insert(x);
    }
    std::sort(std::begin(res), std::end(res));
    return res;
  }
  if (m * 2 <= n) {
    std::vector<bool> used(n, false);
    std::vector<long long> res(m);
    for (int i = 0; i < m; ++i) {
      long long x;
      do {
        x = rnd.next(n);
      } while (used[x]);
      res[i] = x;
      used[x] = true;
    }
    std::sort(std::begin(res), std::end(res));
    return res;
  }
  std::vector<long long> unselect = select(n, n-m);
  std::vector<long long> res;
  long long j = 0;
  for (int i = 0; i < n; ++i) {
    while (j < unselect.size() && unselect[j] < i) ++j;
    if (j < unselect.size() && unselect[j] == i) {
      continue;
    }
    res.push_back(i);
  }
  return res;
}

// select m elements from v
template<class T>
std::vector<T> select(const std::vector<T>& v, const long long m) {
  std::vector<long long> sel = select(v.size(), m);
  std::vector<T> res(m);
  for (int i = 0; i < m; ++i) {
    res[i] = v[sel[i]];
  }
  std::sort(std::begin(res), std::end(res));
  return res;
}

// res_1 + ... + res_gsz = n
// res_1, ..., res_gsz >= min_size
std::vector<long long> grouping(long long n, long long gsz, long long min_size=0) {
  assert(1 <= gsz && min_size * gsz <= n);
  n -= min_size * gsz;
  std::vector<long long> pos = select(n+gsz-1, gsz-1);
  pos.push_back(n+gsz-1);
  std::vector<long long> res(gsz);
  long long prv = -1;
  for (int i = 0; i < gsz; ++i) {
    res[i] = pos[i] - prv - 1 + min_size;
    prv = pos[i];
  }
  return res;
}