相关疑难解决方法(0)

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

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

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

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

给出一个元组列表,其中每个元组由概率和项目组成,我想根据其概率对项目进行抽样.例如,给出列表[(.3,'a'),(.4,'b'),(.3,'c')]我想在40%的时间内对'b'进行采样.

在python中执行此操作的规范方法是什么？

我已经查看了似乎没有适当函数的随机模块和numpy.random,虽然它有一个多项函数但似乎没有以一个很好的形式返回结果来解决这个问题.我基本上在matlab中寻找像mnrnd这样的东西.

非常感谢.

非常感谢所有答案.为了澄清,我不是在寻找如何编写采样方案的解释,而是指出一种简单的方法,从给定一组对象和权重的多项分布中进行采样,或者被告知不存在这样的函数在标准库中,所以应该自己写一个.

我有一个类似于的列表:

[1 2 1 4 5 2 3 2 4 5 3 1 4 2] 

我想从此列表中创建一个x随机元素列表,其中所选元素都不相同.困难的部分是我想通过使用列表理解来做到这一点......如果x = 3,那么可能的结果是:

[1 2 3]
[2 4 5]
[3 1 4]
[4 5 1]

等等...

谢谢!

我应该指定我不能将列表转换为集合.抱歉! 我需要随机选择的数字进行加权.因此,如果1在列表中出现4次,3在列表中出现2次,那么1是被选中的两倍......

我有一组我想随机随机播放的元素,但每个元素都有不同的优先级或权重.因此,具有更大权重的元素必须具有更多的概率才能在结果的顶部.

我有这个数组:

elements = [
  { :id => "ID_1", :weight => 1 },
  { :id => "ID_2", :weight => 2 },
  { :id => "ID_3", :weight => 6 }
]

我想将它洗所以用ID的元素"ID_3"有〜6次以上的概率比元素第一"ID_1"和〜3倍以上的概率比元素"ID_2".

 更新

澄清:一旦你选择了第一个位置,其他元素将使用相同的逻辑争取休息位置.