python - 将一组组合合并成一个更大的集合（反向组合）

我正在尝试创建一个函数，该函数采用子集列表，如果所有组合都存在，则将它们合并为更大的集合。

基本上，假设我们有 n=4（即 index_domain = {0,1,2,3}），我们有以下组合作为输入

[(0, 2), (0, 3), (1, 3), (2, 3)]

该函数应接受此输入并生成以下输出：

[(0, 2, 3), (1, 3)]

因此， (0, 2, 3) 因为所有组合（2 的组合）都存在于输入列表中。(1, 3) 保持原样，因为我们没有其他 1 的组合。

对于一个索引域 D ⊆ ℕ 和输入列表 L，案例的主要特征是：

L 可以是一个空列表。（无关）
L 总是包含 2 的组合，即对，如果不是空的话。
这些对是对称的，并且只有一对包含在 L 中（没有重复）。也就是说，如果一对 (i, j) 应该包含在 L 中，则对 (i, j) 存在于 L 中，并且 (j, i) 永远不会包含，其中 i < j 且 i, j ∈ D。
L, i ∈ D 中永远不存在一对 (i, i)。

简单地说，它是反向的组合（n，2）。我已经搜索了“反向组合”这个主题，但到目前为止我还没有找到合适的资源。我已经考虑过一些选项，例如输入的双重迭代以检查是否所有组合都存在，但这不是最好的方法。我还没有想出一个有效的解决方案。欣赏任何有效解决方案的想法。

谢谢。

标签： pythonpython-3.xalgorithmcombinationsgraph-theory

这个问题似乎等同于在无向图中找到所有团的问题。对于输入中的每一对，在图中添加一条边；当图中有一个集团时，由该集团的顶点表示的每一对值集都存在于输入中。

坏消息是这是一个众所周知的 NP 问题，因此您可能找不到有效的解决方案。好消息是，已经有很多算法可供您用来实施您的解决方案。例如，networkx 包已经实现了一种算法来查找所有 cliques。

所以，你可能应该做的是：