gpt4 book ai didi

algorithm - 如何使用集合中的权重有效地一次随机挑选所有项目?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:31:51 25 4
gpt4 key购买 nike

我有一组对象,我想一次检查一个对象,直到检查完所有对象为止。每个对象都是根据预定义的权重选择的,其中有许多可能重复的对象。最终结果将是集合中项目的有序列表。获取此列表的有效方法是什么?

例如,考虑以下具有指定体积的球:

A: 2
B: 3
C: 25
D: 100

让我们将 4 个 A 球、3 个 B 球、1 个 C 球和 2 个 D 球放入袋中。假设抽到一个特定球的概率与其体积成正比,那么此时抽到一个特定 D 球的概率是 100/242(它们具有相同的重量但不相同)。假设这个D抽到了,继续。此时抽到 C 的几率是 25/142,因为 D 球之前已被移除。假设你在这里画了C球然后继续。继续绘图,直到所有的球都被移除,这样您就有了像 DCDBABBA 这样的序列。

最佳答案

[编辑:更新以添加个人球号]

假设有n k 球不同种类。创建 k -元素数组 (balltype, weight, count)代表初始状态的三元组。当你这样做时,添加每个 weight[i] * count[i]total ,从 0 开始。

首先,为每种球类型设置一个球编号数组:

  1. 对于 i从 1 到 k :
    • 创建 count[i] -元素数组 b[i] , 分配 jb[i][j]对于 1 <= j <= count[i] .

现在随机挑选一个球。可以重复以下步骤n以某种随机顺序挑选所有球的时间:

  1. 选择一个随机整数 r介于 0 和 total 之间- 1 个,包括在内。
  2. 设置p = 0。
  3. 对于 i从 1 到 k :
    • 添加weight[i] * count[i]p .
    • 如果r < p :
      • 我们挑选了一个类型为balltype[i]的球.输出它。
      • 选择一个随机整数 c介于 1 和 count[i] 之间, 包括在内。
      • 输出b[i][c]作为球号。
      • 减少count[i] 1.
      • 设置b[i][c] = b[i][count[i]] .这使未使用的球数保持“密集”。
      • 设置total = total - weight[i] .
      • 停止。

要挑出所有n球将花费 O( nk ) 时间。通过将三元组数组中的最后一个条目移动到位置 i 可以加快大约 2 倍的速度。每当count[i]达到 0(即当所有 i 类型的球都用完时)并减少 n 1,但是对于选择球数的代码继续工作,整个数组 b[n]还必须复制到 b[i] ,或者必须使用另一层间接寻址。

关于algorithm - 如何使用集合中的权重有效地一次随机挑选所有项目?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13941918/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com