不属于集合的等概率样本数

Sample number with equal probability which is not part of a set

我有一个数字 n 和一组数字 S ∈ [1..n]*,大小为 s(远小于 n)。我想以等概率采样一个数字k ∈ [1..n],但是这个数字不允许在集合S.

我正试图在最坏的情况下解决问题 O(log n + s)。我不确定是否可行。

一种天真的方法是创建一个从 1 到 n 的数字数组,排除 S 中的所有数字,然后选择一个数组元素。这将在 O(n) 中 运行 而不是一个选项。

另一种方法可能只是生成随机数 ∈[1..n],如果它们包含在 S 中则拒绝它们。这没有理论上的限制,因为任何数字都可以被多次采样,即使它在集合中也是如此。但平均而言,如果 s 远小于 n.

,这可能是一个实用的解决方案

假设 s 已排序。生成一个介于 1 和 n-s 之间的随机数,称之为 k。我们选择了 {1,...,n} - s 的第 k 个元素。现在我们需要找到它。

对 s 使用二进制搜索来查找 s <= k 的元素数。这需要 O(log |s|)。将此添加到 k。这样做时,我们可能已经通过或到达 s 的其他元素。我们可以通过为我们传递的每个这样的元素增加我们的答案来对此进行调整,我们通过从我们在二进制搜索中找到的点检查 s 的下一个更大的元素来找到它。

例如,n = 100, s = {1,4,5,22},我们的随机数是3。所以我们的方法应该return [2,3,6, 7,...,21,23,24,...,100] 即 6。二分查找发现 1 个元素最多为 3,因此我们递增到 4。现在我们与 s 的下一个更大的元素进行比较是 4 所以增加到 5。重复这个发现 5 in 所以我们增加到 6。我们再次检查 s,看到 6 不在里面,所以我们停止。

例如,n=100,s={1,4,5,22},我们的随机数是4。所以我们的方法应该return[2,3,6, 7,...,21,23,24,...,100] 是 7。二分查找发现 2 个元素最多为 4,所以我们增加到 6。现在我们比较 s 的下一个更大的元素是 5 所以递增到 7。我们再次检查 s,看到下一个数字 > 7,所以我们停止。

如果我们假设 "s is substantially smaller than n" 表示 |s| <= log(n),那么我们将最多递增 log(n) 次,并且在任何情况下最多递增 s 次。


如果 s 未排序,那么我们可以执行以下操作。创建一个大小为 s 的位数组。生成 k。解析 s 并做两件事:1) 计算元素 < k 的数量,称此为 r。同时,如果 k+i 在 s 中,则将第 i 位设置为 1(索引为 0,因此如果 k 在 s 中,则设置第一个位)。

现在,将k递增的次数等于r加上设置的位数就是索引<=递增次数的数组。

例如,n=100,s={1,4,5,22},我们的随机数是4。所以我们的方法应该return[2,3,6, 7,...,21,23,24,...,100] 即 7。我们解析 s 和 1) 注意 1 个元素低于 4 (r=1),以及 2) 将我们的数组设置为 [1 , 1, 0, 0]。我们为 r=1 递增一次,为两个设置位递增两次,最终为 7.

这是O(s)时间,O(s)space.

实际上,拒绝方法似乎是一种实用的方法。 在1...n中生成一个数字,检查是否禁止;重新生成,直到生成的数字不被禁止。

单次拒绝的概率是 p = s/n。 因此,随机数生成的预期数量为 1 + p + p^2 + p^3 + ... which is 1/(1-p),这又等于 n/(n-s).

现在,如果 sn 少很多,甚至更多 s = n/2,这个预期数字最多是 2s 几乎等于 n 使其在实践中不可行。

如果您使用树集检查数字是否在集合中,则将预期时间乘以 log s,如果它是哈希,则仅乘以 1(再次预期值) -放。所以平均时间是 O(1)O(log s) 取决于集合的实现。还有 O(s) 存储集合的内存,但除非集合以某种特殊方式给出,隐含和简洁,否则我看不出如何避免它。

(编辑:根据评论,你只对给定的集合执行一次。 此外,如果我们不走运,并且集合以普通数组或列表的形式给出,而不是一些更高级的数据结构,我们使用这种方法得到 O(s) 预期时间,这仍然适合 O(log n + s)要求。)

如果对无界算法的攻击是一个问题(并且只有当它们确实如此时),该方法可以包括一个回退算法,以应对特定固定次数的迭代未提供答案的情况。 类似于 IntroSort 是 QuickSort,但如果递归深度变得太高(这几乎可以肯定是导致二次 QuickSort 行为的攻击的结果)回落到 HeapSort。

  1. 找出所有在禁止集中且小于或等于 n-s 的数字。称之为数组 A。
  2. 找出所有不在禁止集中且大于 n-s 的数字。称它为数组 B。如果集合已排序,则可以在 O(s) 中完成。
  3. 注意A和B的长度相等,创建映射map[A[i]] = B[i]
  4. 生成数字 t 直到 n-s。如果有map[t]return它,否则returnt

它将在 O(s) 插入到地图 + 1 次查找中工作,平均 O(s) 或 O(s log s)

这是一个具有 O(s) 初始设置的 O(1) 解决方案,它通过将每个不允许的数字 > s 映射到允许的数字 <= s 来工作。

S 为一组不允许的值,S(i),其中 i = [1 .. s]s = |S|

这是一个由两部分组成的算法。第一部分在 O(s) 时间内仅根据 S 构造哈希 table,第二部分在 O(1) 时间内找到随机值 k ∈ {1..n}, k ∉ S,假设我们可以在常数时间内产生连续范围内的均匀随机数。散列 table 可以重新用于新的随机值,也可以用于新的 n(当然假设 S ⊂ { 1 .. n } 仍然成立)。

构造散列,H。首先设置j = 1。然后迭代 S(i)S 的元素。它们不需要分类。如果 S(i) > s,将键值对 (S(i), j) 添加到散列 table,除非 j ∈ S,在这种情况下递增 j 直到不是。最后,递增 j.

要找到一个随机值 k,首先在 s + 1n 范围内生成一个统一的随机值,包括边界值。如果 kH 中的键,则 k = H(k)。即,我们最多进行一次哈希查找以确保 k 不在 S.

Python 生成散列的代码:

def substitute(S):
    H = dict()
    j = 1
    for s in S:
        if s > len(S):
            while j in S: j += 1
            H[s] = j
            j += 1
    return H

为了使实际实现成为 O(s),可能需要将 S 转换为类似 frozenset 的东西,以确保对成员资格的测试是 O(1) 并移动len(S) loop invariant 跳出循环。假设 j in S 测试和插入哈希 (H[s] = j) 是常数时间,这应该具有复杂度 O(s)。

随机值的生成很简单:

def myrand(n, s, H):
    k = random.randint(s + 1, n)
    return (H[k] if k in H else k)

如果只对每个 S 的单个随机值感兴趣,则可以优化算法以改进常见情况,而最坏情况保持不变。这仍然需要 S 位于允许恒定时间 "element of" 测试的散列 table 中。

def rand_not_in(n, S):
    k = random.randint(len(S) + 1, n);
    if k not in S: return k
    j = 1
    for s in S:
        if s > len(S):
            while j in S: j += 1
            if s == k: return j
            j += 1

优化是:仅当随机值在 S 时才生成映射。不要将映射保存到散列 table。找到随机值时将映射生成短路。