n個の要素を含むベクトルからm個の要素をランダムに選択します。

Question

n要素を含むベクトルを持っています。私は、反復せずにベクトルからランダムにm要素のサブセットを選択する必要があります。これを行う最も効率的な方法は何ですか？私は自分のコードでこれを何千回も実行する必要があります。

rand()を使用して、0とnの間の乱数kを生成することです。次にベクトルのk番目の要素を選択し、std::setに挿入します。セットのサイズがmに等しくなるまでこれを続けます。私は今セットがn要素のセットから無作為に選ばれたmのユニークな要素を含んでいることを保証しています。

その他の解決策はありますか？

ありがとうございました。

Answer 1

あなたはFisher-Yates shuffle（M回の反復後に停止）したい：http://ideone.com/3A3cvで

template<class BidiIter > 
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) { 
    size_t left = std::distance(begin, end); 
    while (num_random--) { 
     BidiIter r = begin; 
     std::advance(r, rand()%left); 
     std::swap(*begin, *r); 
     ++begin; 
     --left; 
    } 
    return begin; 
} 

デモ。これは、std::random_shuffleよりもはるかに高速です。セットから数個の乱数しか必要ない場合、N==Mであってもほぼ同じ速度でなければなりません。

Answer 2

あなたがこれを行うことが一つの方法は、ベクトルのすべてのインデックスのリストを作成し、それらをシャッフルして、選択したオブジェクトのインデックスであることを最初nを取ることです。

struct rangegenerator { 
    rangegenerator(int init) : start(init) { } 

    int operator()() { 
     return start++; 
    } 

    int start; 
}; 

vector<T> numbers; // this is filled somewhere else 

vector<int> indices(numbers.size()); 

generate(begin(indices), end(indices), rangegenerator(0)); 

random_shuffle(begin(indices), end(indices)); 

// then take the first n elements of indices and use them as indices into numbers