我在 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。
最佳答案
您至少需要某种伪随机抽样，否则当您重新运行成对抽样代码时，无论是开始还是结束，还是其他地方，总会有某种“偏差”。如果 K 小于 N/2，并且如果 N 不太大(比如 1 亿或更少)，那么您可以使用以下 python 代码，它避免了重复采样调用，因为它一次生成 K 个伪随机对，避免重复
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，那么您将必须有重复项，但您可以通过简单地在循环中重新运行类似于上述 2 行的代码来最大程度地减少与上述类似的重复项。如果 N 是奇数，这会让人头疼，但一个简单的非常接近的近似策略是重复生成 floor(N/2) 对(避免重复)并且每次只留下一个未使用的数字。代码如下:
pairs = []
M = N
if M % 2 == 1:
M -= 1
while len(pairs) < K:
B = random.sample(X,M)
A = zip(B[0:(M/2)],B[(M/2):M])
pairs.extend(A)
pairs = pairs[0:K]
关于python - 从 Python 列表中获取最多的 'diverse' 对集？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17633624/