将一组组合合并为一个更大的组（反向组合）

Question

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

基本上，假设我们有 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 中从来没有一对 (i, i) ？D.

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

谢谢。

Answer 1

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

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

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

1. 将输入转换为图形
2. 使用算法找到派系
3. 将找到的派系转换为集合