0

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

例如，考虑以下具有指定体积的球：

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 这样的序列。

4

1 回答 1

1

[编辑：更新以添加单个球号]

假设有不同类型的n球。k创建一个表示初始状态k的三元组的 -element 数组。(balltype, weight, count)执行此操作时，将每个添加weight[i] * count[i]到total从 0 开始的 。

首先，为每种球类型设置一个球号数组：

  1. i从 1到k:
    • 创建一个count[i]-element array b[i]，分配j给b[i][j]1 <= j <= count[i]。

现在随机挑选一个球。可以重复以下步骤n以随机顺序选择所有球：

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

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

于 2012-12-18T21:51:46.937 回答