5

如何生成范围内(1,n)但不在某个列表中的随机数(i,j)？

示例：范围是(1,500)，列表是[1,3,4,45,199,212,344]。

注意：列表可能未排序

4

4 回答 4

8

拒绝抽样

一种方法是拒绝抽样：

  1. x在 (1, 500) 范围内生成一个数字
  2. x在您的不允许值列表中吗？（可以使用哈希集进行此检查。）
    • 如果是，返回步骤 1
    • 如果不是，x是你的随机值，完成

如果您的允许值集明显大于不允许的值集，这将正常工作：
如果有G可能的好值和可能的坏值，那么您必须从这些值B中采样的预期次数，直到您获得好的价值是（相关几何分布的期望）。（您可以感觉到检查这一点。随着趋于无穷，期望趋于 1。趋于无穷，期望趋于无穷。）xG + B(G + B) / GGB

采样列表

另一种方法是列出L所有允许的值，然后是 sample L[rand(L.count)]。

于 2013-07-12T17:52:37.750 回答
1

当列表长度为 1 时，我通常使用的技术是在 中生成一个随机整数r，[1,n-1]如果r大于或等于该单个非法值，则递增r。

这可以概括为k小长度列表，k但需要对该列表进行排序（您不能以随机顺序进行比较和增量）。如果列表长度适中，那么在排序之后，您可以从 bsearch 开始，并将跳过的值的数量添加到r，然后递归到列表的其余部分。

对于长度列表k，不包含大于或等于 的值n-k，您可以进行更直接的替换：生成随机rin [1,n-k]，然后遍历列表测试是否r等于list[i]。如果它被设置r为n-k+i（这假设list是从零开始的）并退出。

如果某些列表元素位于[n-k,n].

在这一点上，我可以尝试投资一些聪明的东西，但到目前为止，我所拥有的似乎足以满足均匀分布，其值k远小于 n......

  1. 创建两个列表——一个在下面的非法值n-k，另一个是其余的（这可以就地完成）。
  2. 随机r生成[1,n-k]
  3. 对第一个列表应用直接替换方法（如果r然后list[i]设置r为n-k+i并转到步骤 5）。
  4. 如果r在步骤 3 中没有更改，那么我们就完成了。
  5. 对较大值的列表进行排序并使用比较和增量方法。

观察：

  • 如果所有值都在较低的列表中，则不会进行排序，因为没有要排序的内容。
  • 如果所有值都在上面的列表中，则不会进行排序，因为没有任何场合r被移入危险区域。
  • 随着k接近n，上层（已排序）列表的最大大小会增加。
  • 对于给定的k，如果更多值出现在上列表中（排序越大），在下列表中获得命中的机会就会缩小，从而降低需要进行排序的可能性。

细化： 显然，对于 large k，事情变得非常复杂，但在这种情况下，列表中r允许解决的漏洞相对较少。这肯定可以被利用。

如果需要许多具有相同列表和限制的随机值，我可能会提出不同的建议。我希望非法值列表不是先前调用此函数的结果列表，因为如果是，那么您将不想要任何这些——相反，您会想要一个 Fisher-Yates shuffle。

于 2013-07-12T21:38:10.537 回答
1

如前所述，如果可能，拒绝抽样将是最简单的。但是，如果您不想使用它，您可以将范围和不允许的值转换为集合并找出差异。然后，您可以从中选择一个随机值。

假设您希望范围在 [1,n] 但不在 [i,j] 中，并且您希望它们均匀分布。

在 Python 中

total = range(1,n+1)
disallowed = range(i,j+1)
allowed = list( set(total) - set(disallowed) )

return allowed[random.randrange(len(allowed))]

（请注意，这很可能并不完全一致，max_rand%len(allowed) != 0但在大多数实际应用中，这将非常接近）

于 2013-07-17T20:07:31.137 回答
0

我假设您知道如何在 [1, n) 中生成随机数，并且您的列表也像上面的示例一样排序。

假设您有一个包含 k 个元素的列表。制作一个 map(O(logn)) 结构，如果 k 变高，它将确保速度。将列表中的所有元素放入映射中，其中元素值将是键，“好”值将是值。稍后我将解释“好”的价值。因此，当我们拥有地图时，只需在 [1, n - k - p) 中找到一个随机数（稍后我将解释什么是 p），如果该数字在地图中，则将其替换为“好”值。

“GOOD”值 -> 让我们从第 k 个元素开始。它的好值是它自己的值 + 1，因为下一个元素对我们来说是“好”的。现在让我们看看第 (k-1) 个元素。我们假设它的好值再次是它自己的值 + 1。如果这个值等于第 k 个元素，那么第 (k-1) 个元素的“好”值是第 k 个“好”值 + 1。还有您将不得不存储最大的“好”值。如果最大值超过 n，则 p（从上面）将为 p = 最大 - n。

当然，我建议您仅在 k 很大时才这样做，否则@Timothy Shields 的方法是完美的。

于 2013-07-12T18:13:27.953 回答