重複無しでランダムサンプリングする方法がわかりません

Question

c++で、予め用意した配列からランダムで任意の個数抽出するという処理を行いたいのですが、どうすればよいでしょうか？例えば、100個の要素がある配列から10個の要素をランダムに抽出する、という感じです。
個人で考えた方法として、vector形式に保存して毎回shuffle関数で要素の並びをシャッフルし、先頭n個を抽出する、という方法を考えているのですが、shuffle関数が再現性のある処理なのかわからず、適しているかわからないのが現状です。

Answer 1

こんなんでどーぢゃろ

#include <random>
#include <iterator>
#include <algorithm>

/* 
   [first, last) の中からでたらめにひとつ選び、
   末尾要素と入れ替える 
*/
template<typename Iterator, typename Engine>
void pop_random(Iterator first, Iterator last, Engine& eng) {
    std::uniform_int_distribution<int> dist(0, std::distance(first,last)-1);
    std::iter_swap(std::next(first, dist(eng)), std::prev(last));
}

#include <iostream> 
#include <vector>
#include <numeric>

int main() {
  std::vector<int> data(100);
  std::iota(data.begin(), data.end(), 0);
  
  std::mt19937 eng;
  for ( int i = 0; i < 10; ++i ) {
    pop_random(data.begin(), data.end(), eng);
    std::cout << data.back() << std::endl;
    data.pop_back(); // 選んだ要素を取り除く
  }
}

Comments

[yumetodo]

それまったく一様じゃない乱数ですよね。0から99までの連番から10回ランダムに値を抜き取って末尾要素と入れ替えた残りがどうなってるか考えてください。
私の回答の「C++で効率よく重複のない乱数列を生成する - Qiita」のコメント欄見てくるともっといろいろ注意を払う必要があることがあることがわかると思います。

[episteme]

一様じゃない？ でたらめにひとつえらんで袋から取り出したことにならない、と？

[Zuishin]

> 0から99までの連番から10回ランダムに値を抜き取って末尾要素と入れ替えた残りがどうなってるか考えてください。

どうなるんでしょう？
欲しいのは 10 個だけなので、残りの並びがどうなっていようと問題ないはずですが。
フィッシャー–イェーツのシャッフルアルゴリズムの一部ですよね？

[フィッシャー–イェーツのシャッフル - Wikipedia]
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC%E2%80%93%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB

> 1. 1 から N までの数字を書く。
> 2. まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
> 3. 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。

[yumetodo]

distributionがつねに0からになってるからまずいような印象を受けたんですが、大丈夫なのか・・・？混乱してきた

[yominet]

distributionで発生させてるのは「最終的に欲しい数値」ではなく、dataから取り出したい個所

流れを書くと

dist[0～99]の中から1個選ぶ
選んだ番号ｋ1をつかってdata[k1]を操作する（後ろといれかえ、表示、そして削除）
dist[0～98]の中から1個選ぶ。
選んだ番号ｋ2をつかってdata[k2]を操作する（同）
（続く）
の繰り返しだからdistは0から始まらないといけないのでは

[yumetodo]

あー、なるほど

Answer 2

• 配列を重複なく乱数で埋めるには - Qiita
• C++で効率よく重複のない乱数列を生成する - Qiita

昔ドンピシャな内容について論じたことがあります。unordered_setを使ってる例は除外するとして、再現性はいずれもseedにのみ依存します。

Comments

[mmtaro000]

ありがとうございます。参考にさせていただきます。

[yumetodo]

後者の記事のコメント欄では、かなり数学的で私もついていけてない議論が展開されています。数学力に自信があるならそのへんも参考になるかと思います。

Answer 3

非復元抽出は C++17 以前であれば、「シャッフル → 先頭 n 個を取り出す」とすればいいのではないでしょうか。

shuffle - cpprefjp C++日本語リファレンス

C++17 では std::sample() を使えば非復元抽出が行えます。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>

static std::mt19937 engine(0);  // シードを0で固定

std::vector<int> sample(const std::vector<int> &v, size_t n)
{
    if (v.size() < n)
        n = v.size();

    // シャッフルする。
    std::vector<int> v2(v);
    std::shuffle(v2.begin(), v2.end(), engine);

    // 先頭 n 個を取り出す。
    std::vector<int> out(v2.begin(), v2.begin() + n);

    return out;
}

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

    // C++17未満
    {
        std::vector<int> out = sample(v, 10);

        std::for_each(out.begin(), out.end(), [](int x) { std::cout << x << " "; });
        std::cout << std::endl;
    }

    // C++17
    {
        std::vector<int> out;
        std::sample(v.begin(), v.end(), std::back_inserter(out), 10, engine);

        std::for_each(out.begin(), out.end(), [](int x) { std::cout << x << " "; });
        std::cout << std::endl;
    }
}

shuffle関数が再現性のある処理なのかわからず

シャッフルも乱数生成器を利用しているので、乱数生成器のシードを固定すれば再現性は確保できます。

Comments

[mmtaro000]

10000個のうちから抽出するので計算時間もそこまでかからなさそうですね。使用してみます。ありがとうございます。

Answer 4

配列から選んで、重複していたら選び直し、をすればいいだけでしょ。

＃shuffle関数でいいんじゃないかと。

Comments

[mmtaro000]

それが実装簡単そうなのでそうしてみます。ありがとうございます。