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

Question

我正在解一个谜题:

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

我的意思的例子(但要小得多):

字典 = {(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-no-repeat 和最终选择函数。我只是不知道如何实际执行此操作。

感谢阅读!萨拉

编辑:

为了澄清，我写了一个替代代码，将最终函数(基本上是均方根)合并到对集合中。

`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 计算并且只保留最小的一个，我认为这将解决我的组合问题。

Answer 1

如果我理解您的问题，那么您对 ​​(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)))

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