動的偏向ランダム選択アルゴリズム

Question

私はリストからアイテムをランダムに選択するアルゴリズムを実装しようとしていますが、偏っています。そのリストの各要素に対して値の優先度がであるとします。より優先度の高い要素が頻繁に表示されるようにしたいと思います。

もう1つのことは、これらの要素の優先順位が変更されることです。誰かが要素をランダムに選択させるのではなく、要素を選択する場合、その要素の優先順位を一定の要素だけ上げる必要があります。

私は数学的に私の質問をどのようにフレーズするかについてはわかりません。また、どこから始めるべきかわからない。最初の部分を扱うが、要素の優先順位を動的に増やすことは扱っていない記事hereが見つかりました。

私が考えていたアプローチの1つは、要素の優先度が高いほど、より多くのコピーを作成することでした。しかし、これはコンピュータコードで実装することは非常に実現不可能です。

また、数学的な洞察を求めてこの質問をmath.stackexchangeに掲載しました。

注：明らかに、私はsortの実装を探していません。私はちょうど明確な方向性/いくつかの洞察を探しているので、私は自分のアルゴリズムをコード化することができます。私は今の考えることができる可能性のある方法の

Answer 1

一つであり、

はでランダムな値を取得するには二つの配列、優先順位[k]と値[k]は

priority[]={2,1,5,7} 
values[]={"apple","banana","oranges","lollipop"} 

があると仮定優先順位アレイの合計をSとする。この例では、S = 15である。
2.

`cumulative[]= {2,3,8,15} 

3.次に乱数r < = Sを生成し、優先順位アレイの累積的な配列を持っています。 4.7が累積配列の3番目の要素である< 8であるとします。だからあなたは "オレンジ"を返します r = 3の場合は "banana"を返し、r = 10の場合は "lollipop"を返します。

誰かが特に要素を選択した場合、その要素の優先度値を係数kだけ上げるだけです。

と仮定K = 2、及び誰かが上述したのと同じアルゴリズムを使用して、新しいアレイが

priority[]={2,1,7,7} 
values[]={"apple","banana","oranges","lollipop"} 
cumulative={2,3,10,17} 

あり、オレンジの選択は、所望の結果を得るであろう。