一意の値のセットから一意のランダムなサブセットを選択します。

Question

C++。 Visual Studio 2010.

私はstd::vector V個のユニークな要素（重い構造体）を持っています。どのように効率的にM個のランダムでユニークな要素をそれから選ぶことができますか？

など。 {0、1、2、3、4、5、6、7、8、9}と私は3つ選択...

• 4,0、9
• 0、7：Vは、10個の要素が含まれています、8
• これはありません：0,5,5 5 < ---一意ではありません！

STLが好ましい。だから、これは何か？

std::minstd_rand gen; // linear congruential engine?? 
std::uniform_int<int> unif(0, v.size() - 1); 
gen.seed((unsigned int)time(NULL)); 

// ...? 

// Or is there a good solution using std::random_shuffle for heavy objects? 

Answer 1

範囲0, 1, ..., N - 1のランダム置換を作成し、それらの最初のMを選びます。それらをインデックスとして元のベクトルに使用してください。

ランダム置換が容易std::random_shuffleと一緒std::iotaを使用することにより、標準ライブラリで構成されています

std::vector<Heavy> v; // given 

std::vector<unsigned int> indices(V.size()); 
std::iota(indices.begin(), indices.end(), 0); 
std::random_shuffle(indices.begin(), indices.end()); 

// use V[indices[0]], V[indices[1]], ..., V[indices[M-1]] 

あなたがお好みの乱数ジェネレータでrandom_shuffleを供給することができます。詳細については、文書­ men ­をご確認ください。

Answer 2

ほとんどの場合、Kerrekが提供する方法で十分です。しかし、Nが非常に大きく、Mがそれ以下の大きさであれば、以下の方法が好ましいかもしれない。

符号なし整数のセットを作成し、セットのサイズがMになるまで乱数を[0、N-1]の範囲で追加します。次に、それらのインデックスで要素を使用します。

std::set<unsigned int> indices; 
while (indices.size() < M) 
    indices.insert(RandInt(0,N-1)); 

Answer 3

あなたはそれが効率的になりたかったので、私はあなたがその操作を多くの時間を実行する必要が想定して、償却O(M)を得ることができると思います。しかし、このアプローチは再入可能ではありません。

まず、std::vector<...>::size_type（つまり、unsignedが実行する）値のローカル（すなわちstatic）ベクトルを作成します。

std::vector<unsigned> result; 
result.reserver(M); 
for (unsigned i = 0; i < M; i++) { 
    unsigned const r = getRandomNumber(0,N-i); // random number < N-i 
    result.push_back(indices[r]); 
    indices[r] = indices[N-i-1]; 
    indices[N-i-1] = r; 
} 

：

static std::vector<unsigned> indices; 
if (indices.size() < N) { 
    indices.reserve(N); 
    for (unsigned i = indices.size(); i < N; i++) { 
    indices.push_back(i); 
    } 
} 

その後、ランダムにそのベクトルからM固有の番号を選ぶ：あなたはあなたの関数を入力した場合

、Nと一致してN-1に古いサイズの値でそれを埋めるために、ベクターのサイズを変更

あなたの結果はresultベクターにあります。

しかしindicesが再び単調であるように、あなたはまだ、次の実行のためにindicesへの変更を修復する必要があります。

for (unsigned i = N-M; i < N; i++) { 
    // restore previously changed values 
    indices[indices[i]] = indices[i]; 
    indices[i] = i; 
} 

しかし、あなたはそのアルゴリズムをたくさん実行する必要があれば、このアプローチは、のみ有効ですNはそれほど大きくならず、indicesと一緒に暮らすことはできません。