python - 在 1..n 范围内寻找具有均匀概率的 k 个非连续随机数

Question

我试图在 1..n 范围内找到 k 个随机数，这样 k 个数字都不连续。我想出的代码是

def noncontiguoussample(n,k):
    import random
    numbers = range(n)
    samples = []
    for _ in range(k):
        v = random.choice(numbers)
        samples.append(v)
        for v in range(v-1, v+2):
            try:
                numbers.remove(v)
            except ValueError:
                pass

    return samples

更新:我知道此函数不会以均匀概率返回样本。根据我的有限测试，Amber 的以下解决方案满足条件 (a) 样本的各个元素是不连续的，以及 (b) 所有可能的 k 个样本(从 1...n)以均匀概率生成。

Answer 1

如果使用 set，代码会更简单.

import random

def noncontiguoussample(n,k):
    numbers = set(range(1,n+1))
    samples = []
    for _ in range(k):
        v = random.choice(list(numbers))
        samples.append(v)
        numbers -= set([v-1, v, v+1])
    return samples

但是，正如 Michael Anderson 在评论中指出的那样，在 n < 3*k 的情况下，该算法有时会失败。 .

---

一个不会失败(而且速度更快!)的更好算法可能如下所示:

import random

def noncontiguoussample(n,k):
    # How many numbers we're not picking
    total_skips = n - k

    # Distribute the additional skips across the range
    skip_cutoffs = random.sample(range(total_skips+1), k)
    skip_cutoffs.sort()

    # Construct the final set of numbers based on our skip distribution
    samples = []
    for index, skip_spot in enumerate(skip_cutoffs):
        # This is just some math-fu that translates indices within the
        # skips to values in the overall result.
        samples.append(1 + index + skip_spot)

    return samples

最后的数学题是这样的:

• 1，我们可以选择的最小值
• 为我们选择的每个数字加上 1 ( index)，以说明该选择的数字
• 加上我们在 skips 中的位置(总是至少增加一个)

因此，对于循环中的每次迭代，结果总是至少增加 2。