解决这个数组问题的最佳算法是什么？

Question

如果输入是一个类似以下的列表嵌套列表

[[2,1], [1,3], [4,5], [6,8], [4,7]]

如何找到一个/最大的子集，使得其中没有重复/共享元素？

例如，对于此示例，答案可能是：

[2,1], [4,5], [6,8] 

或者

[1,3], [6,8], [4,7] 

但是一个无效的答案将会是

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

因为这里出现了两个1，所以需要去重。

我的当前方法是递归的方法，使用这个思路：在构建子集时，我要么选择第一个元素，要么不选择第一个元素，但这个方法似乎太慢了。

目前的成果是：它只返回最大子集的大小而不是实际的子集，但一旦大小正常工作，获取实际子集应该很容易。

def disjointSets(allSets):
    maxCount = 0
    used = set()
    def findDisjoint(currCount, arr):
        nonlocal maxCount
        if not arr:
            maxCount = max(maxCount, currCount)
            return
        elif arr[0][0] in used or arr[0][1] in used:
            findDisjoint(currCount, arr[1:])
            return
        else:
            used.add(arr[0][0])
            used.add(arr[0][1])
            findDisjoint(currCount + 1, arr[1:])
            used.clear()
            findDisjoint(currCount, arr[1:])
        return
    findDisjoint(0, allSets)
    return maxCount

- Pryver Johnson

---

这是背包问题的变体之一。 - mozway

那么它听起来像是最大基数匹配。 - Kelly Bundy

你的 disjointSets([[1,2],[3,4],[5,6],[1,3],[2,4]]) 输出了 4，哦哦... - Kelly Bundy

只有当你忽略所有集合的大小都是2时，才会出现这种情况。 - Kelly Bundy

这个回答解决了你的问题吗？从列表(l2)中找到最少数量的子列表，这些子列表在另一个列表(l1)中具有最大元素。答案应该包含最少数量的子列表。 - Stef

Answer 1

你看到的是一个图表——数字代表顶点，数字对代表边。

你的问题是找到最大独立边集（不共享顶点的边）。

通常称为最大匹配问题，有着众所周知的解决方案。花式算法是保证找到最佳答案的最简单实用方法。

- Matt Timmermans

---

谢谢！我研究了一下，现在明白了。假设我想扩展这个问题，并使数组的每个元素现在都有3个元素，例如[[1,2,3]，[4,5,6]，等等。使用类似的方法仍然可能吗？ - Pryver Johnson

我不知道有类似的方法适用于三元组。 - Matt Timmermans

Answer 2

正文如下：

正如@MattTimmermans所说，您在这里拥有的是一个无向图，其中每个数字都是一个节点，每对数字是一条边。匹配是一组不共享节点的边，您的任务是找到最大匹配，即包含最多边的匹配。

有一个名为networkx的Python包处理网络，特别是图形。其中有一个方法叫做max_weight_matching，实现了Edmonds'花托算法。

在您的示例中：

import networkx as nx
G = nx.Graph()
G.add_edges_from([[2,1], [1,3], [4,5], [6,8], [4,7]])
out = nx.max_weight_matching(G)

输出：

{(8, 6), (4, 7), (1, 3)}

- user7864386