メモの日々

■ [c++] C++で非復元抽出

集合からN個の要素をランダムに取り出して部分集合を作りたい。現状ではC++の標準ライブラリにはそのような関数が無いみたい。Boostにも見当たらない。

<experimental/algorithm>というヘッダがあればstd::experimental::sample()が使え、GCC 5やClangだと使えそう。が、我が環境のGCC 4.8では使えない。

で、GNUのlibstdc++にはSGI Extensionsというライブラリが含まれていて、<ext/algorithm>をインクルードすると __gnu_cxx::random_sample(), __gnu_cxx::random_sample_n() という関数を使えるようになる。使い方はSGIのサイトのマニュアルで分かる。

• https://www.sgi.com/tech/stl/random_sample.html
• https://www.sgi.com/tech/stl/random_sample_n.html

random_sample()は抽出元コンテナ内での順番を維持しないが、random_sample_n()は維持する。それぞれ、Knuthの"Algorithm R"、"Algorithm S"というアルゴリズムを使っているみたい。

#include <iostream>
#include <numeric>
#include <vector>
#include <ext/algorithm>

int main() {
  std::vector<int> src(20);
  std::iota(src.begin(), src.end(), 0);

  std::vector<int> dst1(10);
  __gnu_cxx::random_sample(src.begin(), src.end(), dst1.begin(), dst1.end());

  std::vector<int> dst2(10);
  __gnu_cxx::random_sample_n(src.begin(), src.end(), dst2.begin(), dst2.size());

  for (auto v : dst1) std::cout << v << " ";
  std::cout << std::endl;
  for (auto v : dst2) std::cout << v << " ";
  std::cout << std::endl;
}

0 19 18 16 4 13 10 7 14 9
0 3 4 5 8 9 10 13 15 19

ライブラリを使わず自分で実装する場合は

• 非復元抽出の高速かつ実装が簡単な方法を考える （睡眠不足？！）

が参考になる。