python - 将一组组合合并成一个更大的集合(反向组合)

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。

简单来说就是 combinations(n, 2) 的反转。我已经搜索过这个主题“反向组合”，但到目前为止我还没有找到合适的资源。我考虑过一些选项，例如对输入进行两次迭代以检查是否所有组合都存在，但这不是最好的方法。我还没有想出一个有效的解决方案。感谢任何有效解决方案的想法。

谢谢。

Answer 1

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

坏消息是这是a very well-known NP-problem ，因此您可能找不到有效的解决方案。好消息是，已经有很多算法可供您用来实现您的解决方案。例如，networkx 包已经实现了 an algorithm to find all cliques .

所以，您可能应该做的是:

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