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

Question

我试图k在范围内找到随机数,1..n使得没有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

如果你使用a,代码会更简单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

然而,正如迈克尔安德森在评论中指出的那样,这种算法有时会失败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),以计算所选号码
• 加上我们在跳过中的位置(总是会增加至少一个)

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