ruby - 基于不同权重随机打乱数组的算法

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]

现在，在 0 之间画一个数字至 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 ，自下而上填充树( post order traversal )。



构建树，填充它并计算 s.w.每个节点在 O(n) 中完成.

现在，您需要反复选择一个介于 0 到权重总和(根的 s.w. 值，在我们的示例中为 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) .

现在，你得到了一个新的二叉树，修改了权重，你准备选择下一个候选者，直到树用尽。