3

我试图找到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）均以均匀概率生成。

4

2 回答 2

6

如果您使用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。

于 2012-09-27T07:07:14.890 回答
0

这是一个不会失败的公正版本。（但比 Ambers 解决方案慢）。如果您给它一个没有解决方案的案例，它将永远循环（但这是可以修复的）。

#A function to check if the given set is OK
def is_valid_choice( s ):
  for x in s:
    if x-1 in s or x+1 in s:
      return False
  return True

#The real function
def noncontiguoussample(n,k):
  while True:
    s = random.sample(xrange(1,n+1),k)
    if is_valid_choice(s):
      return s
于 2012-09-27T09:00:12.500 回答