我有一个项目列表.当我创建列表时,每个项目都有相同的机会被选中.但是,当选择一个项目时,其机会下降,而其他机会上升.如果在此过程中添加了一个新项目,那么在选择它的机会会随之下降的情况下,它应该具有最高的机率.我正在寻找一个可以完成这个C#的好算法.
一般主意：
我有5个项目,随着时间的推移,所有5个项目将被选择20％的时间.我试图将选择保持在接近20％的水平,减少外人.如果存在,将被更多或更少的选择使其重新排列.
解决方法
在这里,我们将设计一个随机数生成器,它具有有利于低值的分布.您可以使用它来更喜欢列表开头的项目.要降低某些被选择的可能性,请将该项目移动到列表中.您有几个选项可以将项目移动到列表中.让我们先来看一下随机变量变换.
index = Int(l*(1-r^(0.5)) # l=length,r=uniform random var between 0 and 1
你会得到一个很酷的分销,大大降低了更大的指数的几率
p(0)=0.09751 p(1)=0.09246 p(2)=0.08769 p(3)=0.08211 p(4)=0.07636 p(5)=0.07325 p(6)=0.06772 p(7)=0.06309 p(8)=0.05813 p(9)=0.05274 p(10)=0.04808 p(11)=0.04205 p(12)=0.03691 p(13)=0.03268 p(14)=0.02708 p(15)=0.02292 p(16)=0.01727 p(17)=0.01211 p(18)=0.00736 p(19)=0.00249
以下是大小为2的列表的分发
0.75139 0.24862
尺寸3
0.55699 0.33306 0.10996
尺寸4
0.43916 0.31018 0.18836 0.06231
现在让我们讨论将项目移动到列表中的两个选项.我测试了两个：
> ToEnd – 将最近选择的项目移动到列表的末尾
>排序 – 保留每个项目已被选择的次数相关联的数组,并将列表从最少排序到最选择.
我创建了一个模拟来从列表中选择并检查每个项目被选中的计数的标准偏差.标准差越低越好.例如,1个模拟的10个项目的列表,其中50个选择创建了传播：
{"a"=>5,"b"=>5,"c"=>6,"d"=>5,"e"=>4,"f"=>4,"g"=>5,"h"=>5,"i"=>6,"j"=>5}
该模拟的标准化是
0.63
随着运行模拟的能力,我然后通过运行模拟500次计算一些元统计,并提供每个方法的平均标准差：ToEnd和Sort.我预计标准偏差对于低数量的选择而言是高的,但实际上对于ToEnd算法,标准偏差随着选择次数的增加而增加.排序方法修复了这个.
Testing ["a","b","c","d","e"] ------------------------- Picks ToEnd (StdDev) Sort (StdDev) 5 0.59 0.57 10 0.76 0.68 15 0.93 0.74 20 1.04 0.74 25 1.20 0.73 30 1.28 0.73 35 1.34 0.74 40 1.50 0.75 45 1.53 0.75 45 1.56 0.77 80 2.04 0.79 125 2.52 0.74 180 3.11 0.77 245 3.53 0.79 320 4.05 0.75 405 4.52 0.76 500 5.00 0.78
以下是一些较大的测试结果.
Testing ["a","e","f","g","h","i","j"] ------------------------- Picks ToEnd (StdDev) Sort (StdDev) 10 0.68 0.65 20 0.87 0.77 30 1.04 0.80 40 1.18 0.82 50 1.30 0.85 60 1.43 0.84 70 1.57 0.87 80 1.65 0.88 90 1.73 0.87 90 1.71 0.87 160 2.30 0.89 250 2.83 0.88 360 3.44 0.88 490 3.89 0.88 640 4.54 0.87 810 5.12 0.88 1000 5.66 0.85
有一个很好的测试框架,我无法抗拒尝试不同的随机数转换.我的假设是,如果我取代立方根,而不是x的平方根,我的标准偏差将会减小.事实上,我确实担心这会减少随机性.在这里,您可以在公式更改时观察几个模拟
index = Int(l*(1-r^(0.33)) # l=length,r=uniform random var between 0 and 1
现在检查实际的选择.正如我所想,它最初是加权到列表的开头.如果你想重量这个重量,你应该在开始之前随机列出你的清单.
StdDev = 0.632455532033676
{"a"=>10,"b"=>10,"c"=>11,"d"=>9,"e"=>10}
a d e c b c e b a d b e c a d d e b a e e c c b d a d c b c e b a a d d b e a e a b c b d c a c e c
StdDev = 0.0
{"a"=>10,"c"=>10,"d"=>10,"e"=>10}
b c d a a d b c b a d e c d e c b e b a e e d c c a b a d a e e b d b a e c c e b a c c d d d a b e
StdDev = 0.632455532033676
{"a"=>9,"e"=>11}
b d a e b c a d c e e b a c a d d c b c e d a e b b a c d c d a e a e e b d c b e a b c b c d d e e
StdDev = 0.0
{"a"=>10,"e"=>10}
a b e d c e a b d c b c c a d b e e b e a d d c e a d b b c c a a a b e d d e c c a b b e a c d e d
StdDev = 0.632455532033676
{"a"=>11,"c"=>9,"e"=>10}
b a d c d c a e b e a e b c d b c a a d e e d c d e c b a b b e d c d b c e a a a d b c e b e a d a
