从Python中的列表中获取最“多样化”的对集？

Question

我在python中有一个长度为N的列表，我想从中选择K对元素，其中一对元素中不允许重复，其中(x,y) == (y,x)（顺序不敏感）。有N个选择2个可能的对，并且K总是显著小于N。从列表中选择最“多样化”和最具代表性的一组对的方法是什么，意思是：（1）表示列表中项目数最多的一组对（并且对任何特定元素都没有偏差），（2）对列表的开始或结尾没有偏差？在

示例：

l = [1,2,3,4,5]

有5种选择2=10种可能的组合。如果我们要求2对（K=2），那么一组好的将是[(1,2),(3,4)]，因为几乎每个元素都出现在列表中，我们没有任何元素的重复。对于K=2，坏的对集应该是：[(1,2),(1,3)]，因为它重用了1元素，并且明显偏向于列表的开头。如果K在这种情况下是2，我们需要重复元素，这是不可避免的，但我想找到一种方法来做到这一点，即代表性/多样性wrt列表。在

我只是在寻找一个高效而简单的启发式方法，不一定要完美。有什么想法吗？在

很高兴使用numpy/scipy来完成这个。在

Answer 1

不管是随机抽样还是随机抽样，至少你会在某个地方随机抽样。如果K小于N/2，并且N不是太大（比如1亿或更少），那么可以使用下面的python代码，因为它一次生成K psuedo随机对，从而避免重复的采样调用

import random

X = range(N)

random.seed() # uses system time to initialize random number generator, or you can pass in a deterministic seed as an argument if you want

# code to use to generate K pairs
A = random.sample(X,2*K) # now you have a list of 2*K unique elements from 0 to N-1
pairs = zip(A[0:K],A[K:(2*K)]) # now you have your pairs

现在，如果K大于N/2，那么必须有重复项，但是可以通过简单地在循环中重新运行类似于上面两行的代码来最小化类似于上面的两行代码。如果N是奇数，这会带来麻烦，但一个简单的非常接近的策略是重复生成floor（N/2）对（避免重复），每次只保留一个未使用的数字。代码如下：

^{pr2}$

Answer 2

从a round-robin tournament获取前K个匹配项？用一个伪随机的Fisher-Yates用一个确定的种子来洗牌，以避免偏向结尾。在