8

私のアルゴリズムでは、ランダムに選択する必要がある 2 つの値がありますが、それぞれを所定の回数選択する必要があります。

これまでのところ、私の解決策は、選択肢をベクトルに正しい回数入れてからシャッフルすることです。C++ の場合:

// Example choices (can be any positive int)
int choice1 = 3; 
int choice2 = 4;

int number_of_choice1s = 5;
int number_of_choice2s = 1;

std::vector<int> choices;
for(int i = 0; i < number_of_choice1s; ++i) choices.push_back(choice1);
for(int i = 0; i < number_of_choice2s; ++i) choices.push_back(choice2);
std::random_shuffle(choices.begin(), choices.end());

次に、イテレータを保持しchoices、新しいイテレータが必要になるたびに、イテレータを増やしてその値を取得します。

これはうまくいきますが、もっと効率的な方法があるようです。使用する各値の数を常に知っているので、値を保存するだけでなく、これを行うためのよりアルゴリズム的な方法があるかどうか疑問に思っています。

4

3 に答える 3

10

不必要に多くのメモリを使用しています。次の 2 つの変数があります。

int number_of_choice1s = 5;
int number_of_choice2s = 1;

単純にランダム化します。

int result = rand() % (number_of_choice1s + number_of_choice2s);
if(result < number_of_choice1s) {
  --number_of_choice1s;
  return choice1;
} else {
  --number_of_choice2s;
  return choice2;
}

これは、200 万回のランダムな呼び出しを非常にうまくスケーリングします。

于 2012-05-10T20:02:26.617 に答える
1

これをもう少し簡単に書くことができます：

std::vector<int> choices(number_of_choice1s, choice1);
choices.resize(number_of_choice1s + number_of_choice2s, choice2);
std::random_shuffle(choices.begin(), choices.end());
于 2012-05-10T20:40:33.317 に答える
0

偏ったランダム分布は、結果のセットに対してある種の順序を維持し（最も選択された選択肢は、次に選択される可能性が低くなります）、偏った結果をもたらします（特に、最初の値は2番目の値に比べて大きいため、最終的には{1,1,1,2,1,1,1,1,2}のようになります。

これが@TomaszNurkiewiczによって書かれたコードによく似ていますが、どちらかの値を選択する可能性が約50/50になる単純な偶数/奇数を使用しているコードです。

int result = rand();

if ( result & 1  &&  number_of_choice1s > 0)
{
number_of_choice1s--;
return choice1;
}else if (number_of_choice2s>0)
{
number_of_choice2s--;
return choice2;
}
else
{
return -1;
}
于 2012-05-10T22:01:59.553 に答える