2

以下に示す重みを使用して、ランダムに生成された数値に重みを割り当てたいと思います。

  0  |  1  |  2  |  3  |  4  |  5  |  6
─────────────────────────────────────────
  X  |  X  |  X  |  X  |  X  |  X  |  X
  X  |  X  |  X  |  X  |  X  |  X  |   
  X  |  X  |  X  |  X  |  X  |     |   
  X  |  X  |  X  |  X  |     |     |   
  X  |  X  |  X  |     |     |     |   
  X  |  X  |     |     |     |     |   
  X  |     |     |     |     |     |

それを行う最も効率的な方法は何ですか？

4

3 に答える 3

3

@Kerrekの答えは良いです。

ただし、重みのヒストグラムがすべて小さな整数ではない場合は、より強力なものが必要です。

[0..1]を重みでサイズ設定された間隔に分割します。ここでは、相対的なサイズ比が7：6：5：4：3：2：1のセグメントが必要です。したがって、1つの間隔単位のサイズは1 /（7 + 6 + 5 + 4 + 3 + 2 + 1）= 1/28であり、間隔のサイズは7 / 28、6 / 28、...1/です。 28。

これらは合計が1になるため、確率分布を構成します。

次に、累積分布を見つけます。

P        x
7/28  => 0
13/28 => 1
18/28 => 2
22/28 => 3
25/28 => 4
27/28 => 5
28/28 => 6

r次に、[0..1]で乱数を生成し、 。のxような最小のものを見つけて、このテーブルでそれを調べますr <= P(x)。これはあなたが望むランダムな値です。

テーブルルックアップはバイナリ検索で実行できます。これは、ヒストグラムに多数のビンがある場合に適しています。

逆累積密度関数を効果的に作成していることに注意してください。これは、逆変換の方法と呼ばれることもあります。

于 2012-10-21T02:45:07.147 に答える
0

To get the distribution you want, first you basically add up the count of X's you wrote in there. You can do it like this (my C is super rusty, so treat this as pseudocode)

int num_cols = 7; // for your example
int max;
if (num_cols % 2 == 0) // even
{
    max = (num_cols+1) * (num_cols/2);
}
else // odd
{
    max = (num_cols+1) * (num_cols/2) + ((num_cols+1)/2);
}

Then you need to randomly select an integer between 1 and max inclusive.

So if your random integer is r the last step is to find which column holds the r'th X. Something like this should work:

for(int i=0;i<num_cols;i++)
{
    r -= (num_cols-i);
    if (r < 1) return i;
}
于 2012-10-21T02:31:58.767 に答える