相关疑难解决方法(0)

假设我有一个n侧加载的模具,当我滚动它时,每个侧面k都有一些概率p _k.我很好奇是否存在静态存储此信息的良好算法(即,对于一组固定的概率),以便我可以有效地模拟模具的随机滚动.

目前,我有一个针对此问题的O(lg n)解决方案.想法是存储所有k的前k个边的累积概率的表,它们生成范围[0,1)中的随机实数并且对表执行二元搜索以获得其累积的最大索引值不大于所选值.我更喜欢这个解决方案,但运行时没有考虑概率似乎很奇怪.特别是,在一方总是出现或值均匀分布的极端情况下,可以使用朴素的方法在O(1)中生成滚动的结果,尽管我的解决方案仍然需要采用多个步骤的对数.

有没有人对如何以某种方式在运行时"自适应"的方式解决这个问题有任何建议？

编辑:基于这个问题的答案,我写了一篇文章,描述了这个问题的许多方法,以及他们的分析.看起来Vose的别名方法的实现给出了Θ(n)预处理时间和每次掷骰的O(1)时间,这确实令人印象深刻.希望这是对答案中包含的信息的有用补充!

这里精美地描述了没有任何权重(相等概率)的选择.

我想知道是否有办法将这种方法转换为加权方法.

我也对其他方法感兴趣.

更新:无需更换的采样

最近我需要从列表中加权随机选择元素,无论是否有替换.虽然有未知加权选择的众所周知和良好的算法,有些用于无替换的加权选择(例如修改算法),我找不到任何好的算法用于替换加权选择.我也想避免使用resevoir方法,因为我选择了列表中的一小部分,这个小部分足够小以容纳在内存中.

有没有人对这种情况下的最佳方法有任何建议？我有自己的解决方案,但我希望找到更高效,更简单或两者兼而有之的方法.

可能重复:
在PHP中按权重生成随机结果？

我有一个Web应用程序,用户可以在其中添加1-20个文本字符串,并为它们指定显示频率的权重.然后,系统将根据定义的权重选择随机字符串.最好的方法是什么？每个字符串的重量范围值是否重要？我可以让用户为每个字符串分配一个数字(0-100)吗？你会如何选择随机字符串？(每个选择都不担心之前选择的内容,每个字符串在每次调用开始时选择的几率(基于权重)相同).

我有一系列对象代表我正在努力开发的游戏中的生物.这些对象具有(以及其他)唯一标识符和产生的权重(或概率).

我正在尝试开发一种随机生成生物的算法,但我没有想出一种使用权重的方法(我真的不知道该怎么做).

有人可以帮忙吗？

生物数组的一个例子可能是:

var creatures = [
    {id: 1, weight: 25},
    {id: 2, weight: 15},
    {id: 3, weight: 5},
    {id: 4, weight: 45},
    {id: 5, weight: 10}
]