从Python中的列表中获取最多'diverse'组对？-Java 学习之路

我有一个长度为N的python列表，我想从中选择K对元素，其中不允许重复一对中的元素，并且 (x,y) == (y,x) （顺序不敏感） . 有N个可能选择2对，并且K总是明显小于N.什么是一个好的确定性（无抽样）方式从列表中选择最多'diverse'和代表性的一对对，意思是：（1）成对的集合表示列表中的最大项目数（并且没有任何特定元素的偏差），（2）并且对的列表没有偏向列表的开头或结尾？

例：

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

有5种选择2 = 10种组合可能 . 如果我们要求2对（K = 2），那么 good 对的对将是 [(1,2),(3,4)] ，因为几乎每个元素都出现在列表中，并且我们没有重复任何元素 . 对于K = 2， bad 对的集合将是： [(1,2),(1,3)] ，因为它需要重复元素，这是不可避免的，但我想找到一种方法来做这个代表性/多样化的列表 .

我只是在寻找一种高效而简单的启发式方法，而不必完美 . 有任何想法吗？

很高兴为此使用numpy / scipy .

2 回答

0
您至少需要某种伪随机抽样，否则当您重新运行对抽样代码时，无论是在开始还是结束时，或者在其他地方，都会存在某种“偏见” . 如果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是奇数，则会产生麻烦但是一个简单的非常接近的近似策略是重复生成楼层（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]
```
回复于 2024-04-29T09:50:51+08:00
1

从round-robin tournament获取前K场比赛？通过具有确定性种子的伪随机Fisher-Yates shuffle置换列表以避免偏向末端 .

回复于 2024-04-29T09:50:51+08:00

从Python中的列表中获取最多'diverse'组对？

2 回答

相关问题