Python：如何在不重复tup内容的情况下生成元组列表的所有组合

Question

我在做一个谜语：

给定一个包含关键字元组的字典：dictionary = {(p,q):n}，我需要生成每个组合的新字典的列表，这样在新字典中p和q都不会重复。在生成此字典列表期间或之后，根据使用字典值的计算，从中选择一个字典作为所需的字典。在

我的意思是（但要小得多）：

dictionary = {(1,1): 1.0, (1,2): 2.0, (1,3): 2.5, (1,4): 5.0, (2,1): 3.5, (2,2): 6.0, (2,3): 4.0, (2,4): 1.0}

变成

listofdictionaries = [{(1,1): 1.0, (2,2): 6.0}, {(1,1): 1.0, (2,3): 4.0}, (1,1): 1.0, (2,4): 1.0}, {(1,2): 2.0, (2,1): 3.5}, {(1,2): 2.0, (2,3): 4.0},等

像：{(1,1): 1.0, (2,1): 3.5}这样的字典是不允许的，因为q重复。在

现在我的可悲故事：我是全新的编码。。。我试图分析我的一些数据。但我也认为这是一个有趣的算法之谜。我写的东西可以用很小的字典，但当我输入一个大的字典时，运行（下面复制）的时间太长了。在我的脚本尝试中，我实际上生成了一个元组组合的列表，我在以后的脚本中使用这些组合来引用我的主字典。我把它复制到下面：

字典元组键由两个列表生成：“ExpList1”和“ExpList2”

#first, I generate all the tuple combinations from my ExpDict dictionary
combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))

#then I generate a list of only the combinations that don't repeat p or q
uniquecombolist = []
for foo in combos:
    counter = 0
    listofp = []
    listofq = []
    for bar in foo:
        if bar[0] in listofp or bar[1] in listofq:
            counter=+1
            break
        else:
            listofp.append(bar[0])
            listofq.append(bar[1])
    if counter == 0:
        uniquecombolist.append(foo)

在生成这个列表之后，我将一个函数应用于所有字典组合（遍历元组列表并从主字典调用它们各自的值），并从该函数中选择结果值最小的组合。在

我还尝试在迭代组合时应用这个函数，选择唯一的p，q，然后检查结果值是否小于前一个值，如果小于则保留（这不是生成列表“uniquecombolist”，我最终只生成最终的元组列表），仍然需要太长时间。在

我认为解决方法在于在组合生成过程中嵌入p，q-无重复和最终选择函数。我只是不知道该怎么做。在

谢谢你的阅读！ 萨拉

编辑：

为了澄清这一点，我编写了一个替代代码，它将最终函数（基本上是均方根）合并到对集合中。在

^{pr2}$

因此，如果我能在集合生成过程中合并RMS计算，只保留最小的一个，我想这将解决我的组合问题。在

Answer 1

这个答案假设您正在尝试生成带有| S |元素的集合，其中S是较小的元组坐标池。较大的池将表示为L

由于集合将包含没有重复元素的| S |对，因此S中的每个元素必须正好出现一次。从这里开始，将L的置换与S的有序元素进行匹配，这将彻底生成所有请求的集合，并且不会重复。在

注意p（| L |，| S |）等于| L |！/（| L |-| S |）！在

根据元组坐标池的大小，可能有太多的排列要枚举。在

复制此枚举的某些代码可能如下所示：

from itertools import permutations 

S, L = range(2), range(4) # or ExpList1, ExpList2
for p in permutations(L, len(S)):
    print(zip(S, p))

总的来说，您的最终代码可能类似于：

^{pr2}$

如果这不能使您达到所需运行时的一个或两个数量级，那么您可能需要考虑一个无法产生最佳解决方案的算法。在

Answer 2

如果我理解你的问题，你会对所有可能的对（p，q）的组合感兴趣，这些组合是关于给定的p和q的一组可能值的。在我的回答中，我假设这些可能的值分别在list_p和{}（我想这就是你在ExpList1和{}中的内容，对吗？）在

min_size = min(len(list_p), len(list_q))

combos_p = itertools.combinations(list_p, min_size)
combos_q = itertools.permutations(list_q, min_size)
prod = itertools.product(combos_p, combos_q)
uniquecombolist = [tuple(zip(i[0], i[1])) for i in prod]

告诉我这是不是你要找的。顺便说一句，欢迎回答，好问题！在

---

编辑：

如果您担心您的列表可能会变得非常庞大，您可以始终使用生成器表达式并对其应用所需的任何函数，例如

^{pr2}$

使用生成器而不是列表时，将根据需要计算值。在这里，因为我们对最小值感兴趣，所以每个值都会被计算出来，除非它是最小值，否则会立即丢弃。在