Python：如何生成元组列表的所有组合，而不重复元组内容。

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不重复和最终选择函数在组合生成期间。我只是在如何实际执行此操作方面遇到了困难。

谢谢阅读！ Sara

编辑：

澄清一下，我编写了一个替代代码，将最终函数（基本上是均方根）与一对集合结合使用。

`combos =(itertools.combinations(ExpDict,min(len(ExpList1),len(ExpList2))))


prevRMSD = float('inf')
for foo in combos:
    counter = 0
    distanceSUM = 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])
        distanceSUM = distanceSUM + RMSDdict[bar]
    RMSD = math.sqrt (distanceSUM**2/len(foo))
    if counter == 0 and RMSD< prevRMSD:
        chosencombo = foo
        prevRMSD = RMSD`

所以如果我在集合生成过程中加入RMS计算并且只保留最小值，我认为这将解决我的组合问题。

- Sara

---

你想生成满足条件的所有可能的一对集合吗？还是可能大小为 n 的一对集合，其中 n 是较小生成列表的长度？ - Jared Goguen

@JaredGoguen 每个对都是集合中的一个单独条目。由于p和q不能重复，因此集合中有n对，因此必须限制为较小生成列表的大小。我想生成给定两个元组对列表（或具有元组键的两个字典）的每个可能集合。 - Sara

我试图查看itertools.combinations的代码，但是我实在无法理解它以便在我的组合条件下工作，甚至我需要应用的最终函数也无法理解。我查看了https://dev59.com/NoHba4cB1Zd3GeqPV8o0，但仍然不太明白它的工作原理。正如我在帖子中所说的，我非常新手（我只写过一个脚本，从未学过计算机科学课程），所以可能我有点力不从心。 - Sara

Answer 1

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

由于集合将包含|S|对没有重复元素，因此必须从S中选择每个元素恰好一次。从这里开始，将L的排列与S的有序元素匹配起来，其中选择了|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))

总的来说，你最终的代码可能会像这样：

S, L = ExpList1, ExpList2
pairset_maker = lambda p: zip(S, p)

if len(S) > len(L):
    S, L = L, S
    pairset_maker = lambda p: zip(p, S)

n = len(S)   
get_perm_value = lambda p: math.sqrt(sum(RMSDdict[t] for t in pairset_maker(p))**2/n)

min_pairset = min(itertools.permutations(L, n), key=get_perm_value)

如果这个算法无法使你的运行时间达到所期望的数量级，那么你可能需要考虑使用不会产生最优解的算法。

- Jared Goguen

---

是的，我已经意识到这一点了，这就是为什么我理想情况下希望在生成组合时应用我的函数...最后我使用一个函数来找到计算最小值的元组集合，因此如果我能将该函数合并到生成唯一集合的代码中，使其检查每个新组合是否比先前的更小，然后保留两者中较小的那个，我认为这可能会起作用？你觉得呢？ - Sara

我正在寻找组合而不是排列。 - Sara

你所描述的一对组合与上面答案中描述的L的排列之间存在一一映射关系。 - Jared Goguen

代码片段是否没有产生您所期望的一组对？ - Jared Goguen

此外，由itertools和生成器生成的对象是惰性的，只有在需要时才会产生元素（即内存中没有巨大的排列列表）。因此，将您的函数应用于元组并仅保留较大的元素不会产生任何效果，我认为。 - Jared Goguen

感谢您的帮助，贾里德。我直到今晚才能回来继续工作。我同意您上面的评论，即可能有太多的排列组合需要枚举...无论我如何去做。我需要想出一种完全不同的方法来实现我想要做的事情。 - Sara

Answer 2

如果我理解您的问题，您对具有唯一p和q值的所有可能配对（p，q）感兴趣，这些值在给定的p和q可能值集合中保持一致。 在我的答案中，我假设这些可能的值分别在list_p和list_q中（我认为这就是您在ExpList1和ExpList2中的情况，我是正确的吗？）

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]

请告诉我这是否是您正在寻找的东西。顺便欢迎来到SO，好问题！

---

编辑：

如果您担心您的列表可能变得非常庞大，您可以随时使用生成器表达式，并将任何所需的函数应用于它，例如：

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)
uniquecombo = (tuple(zip(y[0], y[1])) for y in prod) # this is now a generator expression, not a list -- observe the parentheses

def your_function(x):
    # do whatever you want with the values, here I'm just printing and returning
    print(x)
    return x

# now prints the minimum value
print(min(itertools.imap(your_function, uniquecombo)))

当您使用生成器而不是列表时，值在需要时计算。这里由于我们对最小值感兴趣，每个值都会被计算并立即丢弃，除非它是最小值。

- hugos

---

我认为我仍然会遇到列表过大的问题，无法确定哪组元组对产生了最小的最终值（在将每组输入函数后）。我将编辑上面的帖子以包含我的函数。我将其省略以使此帖子更加通用，但我认为它将有助于读者理解我试图做什么。 - Sara

如果这确实是您想要的，我会尝试更好地解释一下我所做的事情。 - hugos

它优雅地解决了第一轮集合选择问题！谢谢 :) 让我知道您对我上面的编辑有何看法。 - Sara

通用性很重要，这也是你在 Stack Overflow 发帖时应该追求的。我会检查你的编辑。 - hugos

看起来你很关心在应用函数之前生成一个过于庞大的列表。如果是这样，你不需要先生成列表，而是使用生成器表达式。我会向你展示如何做到这一点。 - hugos

抱歉回复晚了。我一直忙于其他学校工作...这个脚本是一个小的副项目/智力游戏。所以我今晚尝试了上面的代码，它可以工作但如果尝试使用超过5或6个条目的列表，它也会导致我的电脑崩溃。我认为我需要采用完全不同的方式来处理，不需要找到并计算列表中的每个组合。使用这种方法，运行时间将随着输入大小的阶乘而增加（正如Jared所指出的）。非常感谢您的帮助，这很有趣！ - Sara