是否有一种有效的方法来限制 Python 中两个列表的唯一组合集？

Question

我有以下代码来生成两个列表之间的每组唯一组合。 换句话说，来自源列表的所有可能的目标匹配集。

from itertools import permutations

def combos(sources, targets):
    assert len(sources) >= len(targets)
    for x in permutations(sources,len(targets)):
        yield list(zip(targets, x))

for x in combos([1,2,3],['a','b']):
    print(x)

结果：

[('a', 1), ('b', 2)]
[('a', 1), ('b', 3)]
[('a', 2), ('b', 1)]
[('a', 2), ('b', 3)]
[('a', 3), ('b', 1)]
[('a', 3), ('b', 2)]

我有一个函数可以计算每个配对的“权重”作为整数。 我计划遍历每个结果列表，将权重加在一起，并找到总权重最小的集合。 理想情况下，我最关心权重最小的一组匹配项。

但是对于大量输入，仅仅迭代排列就变得完全不切实际，Python 就会停滞不前。 我在想我可以通过只考虑基于权重的每个目标的 N 个最佳源匹配来限制它。但是我无法解决如何做到这一点的问题。 有没有：

1. 获得正确答案的更有效方法，或者
2. 在更短的执行时间内限制为“可能正确”的答案？

Answer 1

sources

和

targets

之间的关系（连接和权重）是 graph 的边。具体来说，在您的情况下，它是一个bipartite graph，因为两个独立组的节点之间只有边（例如，没有

a-b

或

0-2

边）。

在不共享节点的情况下找到图中所有可能形成边的方法的问题称为“匹配”，如

[b-1, a-3]

。如果给每条边分配权重，想找到总权重最小的匹配，就叫最小权重匹配。

二分图的最小（或最大）权重匹配称为分配问题，有几种算法可以在多项式时间内求解，如匈牙利算法和Karp算法 .

一般情况（非二部图）的最小权重匹配的解决方案要难得多，我知道的唯一算法是复杂的blossom算法.

有一个优秀的库可以在名为 networkx 的 python 中处理图形。这是有关如何使用它来解决您的问题的示例。我正在使用函数

hash

作为权重，但您可以使用您的逻辑要求代替。

import networkx as nx

graph = nx.complete_bipartite_graph(range(5), 'abcdefg')
sources, targets = nx.bipartite.sets(graph)

for a, b in graph.edges():
    graph.edges[a, b]["weight"] = hash((a, b)) # whatever logic you have
    print(a, b, graph.edges[a, b])

matching = nx.bipartite.minimum_weight_full_matching(graph)
result = [(a, matching[a], graph.edges[a, b]["weight"]) for a in sources]

print("minimum weight match", *result, sep="\n")
print("minimum weight sum\n", sum(w for _,_,w in result))
# minimum weight match:
#    (0, 'e', -5652564962590522143)
#    (1, 'c', -2359047611522945134)
#    (2, 'b', 3092743657457074790)
#    (3, 'a', 5054043193701197225)
#    (4, 'g', -7940909611028334467)
# minimum weight sum: -7805735333983529729