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

Answer 1

这是一种方法，通过在0 to n*(n-1)/2 - 1范围内取一个数字并将其解码为0 to 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)]

数学难以解释，但是k定义中的decode是通过求解二次方程得到的，该方程给出triangular numbers的<= i数，i落在三角数序列中，告诉你如何解码一个唯一的从中对。关于这个解码的有趣之处在于它根本不使用n，而是实现从自然数集（从0开始）到所有自然数对集合的一对一对应关系。

Answer 2

您可以使用combinations生成所有对，并使用sample随机选择。不可否认只是在“不太多打字”的意义上懒惰，而不是在使用发电机而不是列表意义:-)

from itertools import combinations
from random import sample

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

如果你想提高性能，你可以通过研究这个Python random sample with a generator / iterable / iterator来使它变得懒惰

你要采样的发电机是这样的：combinations(range(1,n)

Answer 3

我不认为你的任何东西都可以改进。毕竟，随着你的m越来越接近极限n(n-1)/2，你有更薄更薄的机会找到看不见的对。

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

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

现在你必须确定m的阈值，它确定它应该去哪个代码路径。你需要一些数学来找到正确的权衡。