基于不同权重随机调整数组的算法 [英] Algorithm to shuffle an Array randomly based on different weights

问题描述

我有一些要随机洗牌的元素，但是每个元素都有不同的优先级或权重。因此，权重较大的元素必须具有更多的概率才能位于结果的顶部。

我有这个数组：

 元素= [
 {：id =>  ID_1，：weight => 1}，
 {：id =>  ID_2，：weight => 2}，
 {：id =>  ID_3，：weight => 6} 
] 
  

我想将其洗牌，所以id为<$ c的元素$ c> ID_3 比元素 ID_1 和〜3倍于元素 ID_2 的概率。

更新

说明：一旦选择了第一个位置，其余元素将使用相同的逻辑战斗。

解决方案

我可以想到两种解决方法，尽管我的直言告诉我应该对）。

构建树，填充树并为每个节点计算 sw 在 O（n）<中完成/ code>。

现在，您需要迭代地选择一个介于0到权重总和之间的随机数（在本例中为25的根的sw值） ）。将该数字设为 r ，然后为每个此类数字找到匹配的节点。

以递归方式找到匹配的节点

 如果`r< root.left.sw`：
转到左儿子，然后重复。 
，如果`r< root.left.sw + root.w`：
您要查找的节点是根，请选择它。 
 else：
使用`r = r-root.left.sw-root.w`进入`root.right` 
  

例如，选择 r = 10 ：

  r< root.left.sw是吗？是。递归调用r = 10，root = B（左孩子）
是r  r   

这是通过 O（h）= O（logn）。

现在，您需要删除该节点，并重置树的权重。

一种删除方法，确保树的对数权重类似于二进制堆：用最右边的底部节点替换选定的节点，删除最右边的底部节点，然后重新平衡从

第一个开关：

然后重新计算：

请注意，仅需要对两个路径进行重新计算，每个深度最多为 O（logn）（图中节点显示为橙色的节点），因此删除和重新计算也为 O（logn）。

现在，您有了一个新的二叉树，其权重已修改，您可以选择下一个候选对象，直到树被耗尽为止。

I have a collection of elements that I want to shuffle randomly, but every element has a different priority or weight. So the element with bigger weight has to have more probabilities to be on the top of the result.

I have this Array:

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

And I want to shuffle it so the element with id "ID_3" has ~6 times more probabilities to be first than the element "ID_1" and ~3 times more probabilities than the element "ID_2".

 Update

Clarification: once you have chosen the first position the other elements will fight for the rest positions using the same logic.

解决方案

I can think of two approaches to solve it, though my gut tells me there should be modification for Fisher-Yates to achieve it even better:

O(n*W) solution: (simple to program)

First approach, create duplicates according to the weight (same as your approach), and populate a new list. Now run a standard shuffle (fisher-yates) on this list. Iterate the list and discard all duplicates, and keep only the first occurance of each element. This runs in O(n*W), where n is the number of elements in the list, and W is the average weight (pseudo-polynomial solution).

---

O(nlogn) solution: (significantly harder to program)

Second approach would be to create a list of sum of weights of the elements:

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

Now, draw a number, between 0 to sum[n], and chose the first element whose sum is greater/equals this random number.
This will be the next element, discard the element, recreate the list, and repeat.

This runs in O(n^2*logn)

It can be further enhanced by creating a binary tree rather than a list, where each node also stores the value of weights of the entire subtree.
Now, after choosing an element, find the matching element (whose sum up to him is the first one higher than the random selected number), delete the node, and recalculate the weights on the path to the route.
This will take O(n) to create the tree, O(logn) to find the node at each step, and O(logn) to recalculate the sum. Repeat it until the tree is exhausted, and you get O(nlogn) solution.
The idea of this approach is very similar to Order Statistics Trees, but using the sum of weights rather than the number of descendants. The search and balancing after deletion will be done simiarly to order statistics tree.

---

Explanation to constructing and using the binary tree.

Assume you have elements=[a,b,c,d,e,f,g,h,i,j,k,l,m] with weights=[1,2,3,1,2,3,1,2,3,1,2,3,1]

First construct an almost full binary tree, and populate the elements in it. Note that the tree is NOT Binary search tree, just a regular tree, so order of elements does not matter - and we won't need to maintain it later on.

You will get something like the following tree:

Legend: w - weight of that node, sw - sum of weight for the entire subtree.

Next, calculate sum of weights for each subtree. Start from the leaves, and calculate s.w = w. For every other node calculate s.w = left->s.w + right->s.w, filling the tree from the bottom up (post order traversal).

Building the tree, populating it, and calculating s.w. for each node is done in O(n).

Now, you iteratively need to chose a random number between 0 to sum of weights (the s.w. value of the root, in our case 25). Let that number be r, and find for each such number the matching node.
Finding the matching node is done recursively

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`

Example, chosing 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.

This is done in O(h) = O(logn) per iteration.

Now, you need to delete that node, and reset the weights of the tree.
One approach to deleting that ensures the tree is in logarithmic weight is smilar to binary heap: Replace the chosen node with the bottom rightest node, remove the new rightest bottom node, and rebalance the two branches going from the two involved nodes to the tree.

First switch:

Then recalculate:

Note that recalculation is needed only to two paths, each of depth at most O(logn) (the nodes colored orange in the pic), so deletion and recalculation is also O(logn).

Now, you got yourself a new binary tree, with the modified weights, and you are ready to choose the next candidate, until the tree is exhausted.

这篇关于基于不同权重随机调整数组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！