Python：保持最小距离的范围内的随机数字列表

Question

假设此代码 random.seed(42) random.sample(range(0,40), 4) 输出：[7, 1, 17, 15] 我应该在此代码中更改什么以生成随机数，其中列表中任意两个数字之间的最小距离至少为 10 或更多。类似的东西[0, 10, 25, 39] or [0, 12, 23, 38 ]。可能的重复是this。谢谢。

Answer 1

排序案例的一行解决方案

这是一个简单的单行，它以相同的可能性生成所有可能性：

[9*i + x for i, x in enumerate(sorted(random.sample(range(13), 4)))]

一些示例输出：

[2, 16, 26, 38]
[0, 10, 25, 35]
[2, 12, 25, 36]
[0, 13, 26, 39]
[1, 14, 24, 34]
[1, 11, 29, 39]
[0, 13, 26, 39]
[1, 12, 27, 38]

输出总是按排序顺序生成；如果这不是您想要的，您可以轻松地向结果添加随机播放（或参见下文了解一般解决方案）。

解释：如果[a, b, c, d]是一个满足你要求的有序列表，那么[a, b-9, c-18, d-27]是一个长度为 4 的有序样本 from range(13)，反之亦然。所以你需要做的就是从 生成样本range(13)，对它们进行排序，然后重新添加必要的倍数9以获得至少10相距的值。

一般未排序的解决方案

这是一个不需要对随机样本进行排序的通用解决方案。相反，我们计算样本元素的等级并使用它们来计算必要的偏移量。

import random

def ranks(sample):
    """
    Return the ranks of each element in an integer sample.
    """
    indices = sorted(range(len(sample)), key=lambda i: sample[i])
    return sorted(indices, key=lambda i: indices[i])

def sample_with_minimum_distance(n=40, k=4, d=10):
    """
    Sample of k elements from range(n), with a minimum distance d.
    """
    sample = random.sample(range(n-(k-1)*(d-1)), k)
    return [s + (d-1)*r for s, r in zip(sample, ranks(sample))]

和一些示例输出：

>>> sample_with_minimum_distance()
[17, 27, 3, 38]
>>> sample_with_minimum_distance()
[27, 38, 10, 0]
>>> sample_with_minimum_distance()
[36, 13, 1, 24]
>>> sample_with_minimum_distance()
[1, 25, 15, 39]
>>> sample_with_minimum_distance()
[26, 12, 1, 38]

“便宜的把戏”解决方案

如果原始问题中的各种常量是固定的（人口range(40)，长度为 4 的样本，最小距离为 10），那么有一个明显的廉价技巧：只有715可能不同的排序样本，因此只需预先创建一个包含所有然后每次需要生成样本时，使用random.choice.

对于这一代，我们可以选择一个效率极低但显然正确的蛮力解决方案：

>>> import itertools
>>> all_samples = [  # inefficient brute-force solution
...     sample for sample in itertools.product(range(40), repeat=4)
...     if all(x - y >= 10 for x, y in zip(sample[1:], sample))
... ]
>>> len(all_samples)
715

这仍然足够快，在我的机器上只需要几秒钟。或者，我们可以使用与上述相同的双射来做一些更精致和直接的事情。

>>> all_samples = [
...     [9*i + s for i, s in enumerate(sample)]
...     for sample in itertools.combinations(range(13), 4)
... ]
>>> len(all_samples)
715

无论哪种方式，我们只生成一次样本列表，然后random.choice在每次需要时选择一个：

>>> random.choice(all_samples)
(1, 11, 21, 38)
>>> random.choice(all_samples)
(0, 10, 23, 33)

当然，这个解决方案不能很好地扩展：对于range(100)最小距离为 5 的7 个样本，有超过 20 亿个可能的不同排序样本。

均匀性演示

我之前声称，单行以相同的可能性产生所有可能性（当然，假设随机数的完美来源，但 Python 的 Mersenne Twister 足够好，我们不太可能在测试中检测到核心生成器产生的统计异常以下）。这是这种一致性的演示。

首先，为了方便起见，我们将单行代码包装在一个函数中。我们还将更改它以返回 atuple而不是 a list，因为下一步我们想要一些可散列的东西。

>>> def sorted_sample():
...     return tuple(9*i + x for i, x in
...                  enumerate(sorted(random.sample(range(13), 4))))

现在我们生成 1000 万个样本（这将需要几分钟），并计算每个样本出现的频率：

>>> from collections import Counter
>>> samples = Counter(sorted_sample() for _ in range(10**7))

几个快速检查：

>>> len(samples)
715
>>> 10**7 / 715
13986.013986013986
>>> samples[0, 10, 20, 30]
14329
>>> samples[0, 11, 22, 33]
13995
>>> min(samples.values())
13624
>>> max(samples.values())
14329

我们收集了 715 种不同的组合，一点点数学知识告诉我们这正是我们期望的数字（13 选 4），因此在均匀分布的情况下，我们希望每个组合大约出现10**7 / 715几次，或者大约 14000 次. 我们上面检查的两个组合都在 14000 左右，出现的最小和最大计数也是如此，但毫不奇怪，存在一些随机变化。

这种随机变化是否在可接受的范围内？为了找出答案，我们可以使用 进行卡方检验p = 0.01。我们的零假设是我们从中抽取的总体是统一的：即，我们的代码以相同的可能性生成每个可能的样本。

SciPy 使一致性的卡方检验变得容易：

>>> from scipy.stats import chisquare
>>> chisquare(list(samples.values()))
Power_divergenceResult(statistic=724.682234, pvalue=0.3825060783237031)

我们得到的 p 值不小于 0.01，因此我们无法拒绝原假设：也就是说，我们没有非均匀性的证据。