0

我在 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。

4

2 回答 2

1

您至少需要某种伪随机采样，否则当您重新运行您的配对采样代码时，无论是在开始或结束，还是在其他地方，总会存在某种“偏差”。如果 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]
于 2013-07-14T00:40:52.417 回答
0

参加循环赛的前 K 场比赛？通过使用确定性种子的伪随机 Fisher-Yates 洗牌来置换列表，以避免偏向末端。

于 2013-07-13T20:30:09.930 回答