Python获取随机唯一的N对

Question

假设我有一个range(1, n + 1)。我想要得到m个唯一的对。

我发现，如果需要的对数接近于n(n-1)/2（最大可能的对数），那么不能简单地每次生成随机对，因为它们会开始互相覆盖。我正在寻找一种比较懒惰的解决方案，在Python世界中非常高效。

我目前的尝试：

def get_input(n, m):

    res = str(n) + "\n" + str(m) + "\n"
    buffet = range(1, n + 1)
    points = set()

    while len(points) < m:
        x, y = random.sample(buffet, 2)
        points.add((x, y)) if x > y else points.add((y, x)) # meeh

    for (x, y) in points:
        res += "%d %d\n" % (x, y);

    return res

- Afonso Matos

Answer 1

您可以使用“组合”来生成所有的配对，使用“样本”来进行随机选择。诚然，“懒惰”只在“不用打太多字”方面体现，而不是使用生成器而不是列表的意义上。 :-)

from itertools import combinations
from random import sample

n = 100
sample(list(combinations(range(1,n),2)),5)

如果你想提高性能，可以通过学习这个Python随机样本生成器/可迭代对象/迭代器来使其变得更好。

你需要从下面的生成器中进行抽样：combinations(range(1,n)

- Christian Sloper

Answer 2

这里有一种方法，它通过将范围在 0 到 n*(n-1)/2 - 1 内的数字解码为范围在 0 到 n-1 的唯一一对项目。我为了方便使用基于0的数学，但如果需要，您当然可以将所有返回的对都加1：

import math
import random

def decode(i):
    k = math.floor((1+math.sqrt(1+8*i))/2)
    return k,i-k*(k-1)//2

def rand_pair(n):
    return decode(random.randrange(n*(n-1)//2))

def rand_pairs(n,m):
    return [decode(i) for i in random.sample(range(n*(n-1)//2),m)]

例如：

>>> >>> rand_pairs(5,8)
[(2, 1), (3, 1), (4, 2), (2, 0), (3, 2), (4, 1), (1, 0), (4, 0)]

这个数学问题很难简单地解释，但是在“decode”的定义中，k的值是通过解一个二次方程得到的，该方程给出了小于等于i的三角形数的数量，而i在三角形数序列中的位置告诉你如何从中解码出一个唯一的对。这个decode的有趣之处在于它根本不使用n，而是实现了从自然数集合（从0开始）到所有自然数对集合的一一对应关系。

- John Coleman

---

有更全面的解释的链接吗？谢谢。 - Afonso Matos

顺便说一下，这是完美的。 - Afonso Matos

@AfonsoMatos 我不知道有没有链接。我从枚举 (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3) 开始（如果它不依赖于 n，这就是你需要的枚举类型），注意到以 1 开头的有 1 个，以 2 开头的有 2 个，以此类推。为了从 i 中得到这对数，我需要知道 i 在哪个“块”中。例如，i = 7 在 4 块中 因为 1+2+3 <= 7 < 1+2+3+4，这相当于 3(3-1)/2 <= 7 < 4(4-1)/2。如果你解方程 7 = k(k-1)/2 并转换成整数，你就能得到 k。再进行一些代数运算，你就能得到另一个索引。 - John Coleman

Answer 3

我认为你的代码已经无法再进行改进。毕竟，随着你的 m 越来越接近极限 n(n-1)/2，你发现未见过的配对的机会越来越少。

我建议分成两种情况：如果 m 很小，使用你的随机方法。但如果 m 足够大，尝试

 pairs = list(itertools.combination(buffet,2))
 ponits = random.sample(pairs, m)

现在，您需要确定阈值m，以确定它应该走哪个代码路径。您需要进行一些数学计算，以找到正确的权衡。

- adrtam