基于不同权重随机混洗阵列的算法

Question

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

我有这个数组:

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".

 更新

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

Answer 1

我可以想到两种方法来解决它,虽然我的直觉告诉我应该修改Fisher-Yates来实现它更好:

O(n*W)解决方案:(简单编程)

第一种方法,根据权重创建重复项(与您的方法相同),并填充新列表.现在在这个列表上运行一个标准的shuffle(fisher-yates).迭代列表并丢弃所有重复项,并仅保留每个元素的第一次出现.这运行于O(n*W),n列表中元素的数量,并且W是平均权重(伪多项式解).

O(nlogn)解决方案:( 难以编程)

第二种方法是创建元素权重总和列表:

sum[i] = weight[0] + ... + weight[i]

现在,在0to 之间绘制一个数字,sum[n]并选择第一个元素,该元素的sum大于/等于该随机数.
这将是下一个元素,丢弃元素,重新创建列表,然后重复.

这运行于 O(n^2*logn)

可以通过创建二叉树而不是列表来进一步增强它,其中每个节点还存储整个子树的权重值.
现在,在选择一个元素之后,找到匹配元素(其总和是他的第一个高于随机选择的数字),删除节点,并重新计算路径路径上的权重.
这将O(n)创建树,O(logn)在每一步找到节点,并O(logn)重新计算总和.重复它直到树耗尽,然后你得到O(nlogn)解决方案.
这种方法的想法与Order Statistics Trees非常相似,但使用权重之和而不是后代数.删除后的搜索和平衡将与订单统计树类似地完成.

构造和使用二叉树的说明.

假设你有elements=[a,b,c,d,e,f,g,h,i,j,k,l,m]与weights=[1,2,3,1,2,3,1,2,3,1,2,3,1]

首先构造一个几乎完整的二叉树,并填充其中的元素.请注意,树不是二进制搜索树,只是常规树,因此元素的顺序无关紧要 - 我们以后不需要维护它.

您将获得类似以下树的内容:

图例: w - 该节点的权重,整个子树的权重的sw和.

接下来,计算每个子树的权重总和.从树叶开始,计算s.w = w.对于每个其他节点计算s.w = left->s.w + right->s.w,从下往上填充树(后订单遍历).

构建树,填充树以及计算s.w.每个节点都是在O(n).

现在,您需要迭代地选择0到权重之和的随机数(根的sw值,在我们的例子中为25).设这个数字r,并为每个这样的数字找到匹配节点.
寻找匹配节点是递归完成的

if `r< root.left.sw`:
   go to left son, and repeat. 
else if `r<root.left.sw + root.w`:
   the node you are seeking is the root, choose it. 
else:
   go to `root.right` with `r= r-root.left.sw - root.w`

例子,选择r=10:

Is r<root.left.sw? Yes. Recursively invoke with r=10,root=B (left child)
Is r<root.left.sw No. Is r < root.left.sw + root.w? No. Recursively invoke with r=10-6-2=2, and root=E (right chile)
Is r<root.left.sw? No. Is r < root.left.sw + root.w? Yes. Choose E as next node.

这是在O(h) = O(logn)每次迭代中完成的.

现在,您需要删除该节点,并重置树的权重.
一种删除方法确保树具有对数权重对于二进制堆很简单:用最右下方的节点替换所选节点,删除新的最右下节点,并重新平衡从两个相关节点到树的两个分支.

第一个开关:

然后重新计算:

请注意,只需要重新计算两条路径,每条路径最多为深度O(logn)(图中的节点为橙色),因此删除和重新计算也是如此O(logn).

现在,你得到了一个新的二叉树,修改了权重,你就可以选择下一个候选者,直到树用完为止.