ruby – 基于不同权重随机混洗数组的算法

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

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

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

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

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

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

这在O(n ^ 2 * logn)中运行

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

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

假设你有元素= [a,b,c,d,e,f,g,h,i,j,k,l,m],权重= [1,2,3,1,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).

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