5

重複の可能性：
O（1）の一意の乱数？
Cプログラミング言語の整数配列の一意の乱数

サイズが決まっていstd::vectorないユニークな要素があります。このベクトルから20個のユニークでランダムな要素をフェッチしたいと思います。「一意」とは、同じインデックスを複数回フェッチしたくないことを意味します。現在、私がこれを行う方法は、を呼び出すことstd::random_shuffleです。ただし、これには、ベクトル全体（1000を超える要素が含まれる場合があります）をシャッフルする必要があります。ベクトルを変更してもかまいませんが（スレッドロックを使用する必要がないため、変更しない方がよいです）、最も重要なのは、これを効率的にしたいということです。必要以上にシャッフルするべきではありません。

に部分的な範囲を渡すことを検討しましたstd::random_shuffleが、要素のサブセットのみをシャッフルすることに注意してください。つまり、その範囲外の要素は使用されません。

ヘルプをいただければ幸いです。ありがとうございました！

注：私はVisual Studio 2005を使用しているため、C++11の機能とライブラリにアクセスできません。

4

4 に答える 4

8

フィッシャーイェーツhttp://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffleを使用できます

フィッシャー-イェーツシャッフル（ロナルドフィッシャーとフランクイェーツにちなんで名付けられました）は、クヌースシャッフル（ドナルドクヌースにちなんで）とも呼ばれ、有限セットのランダム順列を生成するアルゴリズムです。代わりに、Sattoloのアルゴリズムとして知られるFisher-Yatesシャッフルの変形を使用して、長さnのランダムサイクルを生成することができます。適切に実装されると、フィッシャー-イェーツシャッフルは偏りがないため、すべての順列が同じように発生する可能性があります。最新バージョンのアルゴリズムもかなり効率的であり、シャッフルされるアイテムの数に比例する時間のみを必要とし、追加のストレージスペースは必要ありません。フィッシャー-イェーツシャッフルの基本的なプロセスは、帽子から番号の付いたチケット、またはデッキからカードをランダムに選び、残りがなくなるまで次々に選ぶのと似ています。

この擬似コードは機能するはずだと思います（1つずつ間違える可能性があるので、もう一度確認してください！）：

std::list chosen; // you don't have to use this since the chosen ones will be in the back of the vector
for(int i = 0; i < num; ++i) {
  int index = rand_between(0, vec.size() - i - 1);
  chosen.push_back(vec[index]);
  swap(vec[index], vec[vec.size() - i - 1]);
}
于 2012-12-07T23:13:22.240 に答える
8

nベクトルからサイズmのランダムサンプルが必要です。

rand（a）が0..a-1ユニフォームを返すようにします

for (int i = 0; i < m; i++)
    swap(X[i],X[i+rand(n-i)]);

X[0..m-1]はランダムサンプルになりました。

于 2012-12-07T23:15:24.897 に答える
3

ループを使用して乱数をaに入れ、 20に達しstd::setたときに停止します。size()

std::set<int> indexes;
std::vector<my_vector::value_type> choices;
int max_index = my_vector.size();
while (indexes.size() < min(20, max_index))
{
    int random_index = rand() % max_index;
    if (indexes.find(random_index) == indexes.end())
    {
        choices.push_back(my_vector[random_index]);
        indexes.insert(random_index);
    }
}

乱数の生成は私の頭に浮かんだ最初のものです。もっと良いものを自由に使用してください。

于 2012-12-07T23:11:39.783 に答える
0 
#include <iostream>
#include <vector>
#include <algorithm>

template<int N>
struct NIntegers {
  int values[N];
};
template<int N, int Max, typename RandomGenerator>
NIntegers<N> MakeNRandomIntegers( RandomGenerator func ) {
  NIntegers<N> result;
  for(int i = 0; i < N; ++i)
  {
    result.values[i] = func( Max-i );
  }
  std::sort(&result.values[0], &result.values[0]+N);
  for(int i = 0; i < N; ++i)
  {
    result.values[i] += i;
  }
  return result;
};

使用例：

// use a better one:
int BadRandomNumberGenerator(int Max) {
  return Max>4?4:Max/2;
}
int main() {
  NIntegers<100> result = MakeNRandomIntegers<100, 500>( BadRandomNumberGenerator );
  for (int i = 0; i < 100; ++i) {
    std::cout << i << ":" << result.values[i] << "\n";
  }
}

各数値を最後の数値よりも最大で1小さくします。それらを並べ替えてから、各値をその前の整数の数で増やします。

テンプレートのものは単なるトレードドレスです。

于 2012-12-07T23:21:15.137 に答える