不相交子集的最大可能数目

Question

我得到了一组列表，例如：

[[0, 1, 3], [0, 2, 12], [6, 9, 10], [2, 4, 11], [2, 7, 13], [3, 5, 11], [3, 7, 10], [4, 10, 14], [5, 13, 14]]

我需要找到这个列表包含的不相交子集的最大数目。在本例中，答案是4。在

另一个例子是： [[0, 1, 12], [0, 4, 11], [0, 7, 19], [0, 15, 17], [0, 16, 18], [1, 4, 16], [1, 13, 25], [2, 4, 23], [2, 10, 27], [2, 12, 19], [2, 14, 22], [2, 16, 20], [3, 6, 13], [3, 7, 22], [3, 10, 14], [3, 20, 26], [4, 7, 13], [4, 17, 22], [5, 7, 25], [5, 9, 22], [5, 10, 21], [5, 11, 23], [5, 12, 20], [5, 13, 16], [5, 14, 15], [6, 7, 17], [6, 10, 23], [7, 11, 20], [7, 14, 27], [7, 18, 23], [8, 12, 26], [8, 14, 17], [8, 22, 23], [11, 12, 18], [12, 17, 21], [12, 23, 25], [13, 19, 20], [13, 21, 24], [18, 20, 25], [18, 24, 26], [19, 24, 27]] 在这里，答案是8。在

我知道这个问题是NP难的，所以我想出了一个半蛮力的方法。在

我首先通过向不相交的子集列表中添加子集来获得近似答案。所以，每当我迭代一个集合时，我会检查它是否已经存在于不相交的子集列表中。如果不是的话，我就把它添加到列表中。这给了我一个大概的数字，可能是也可能不是最大可能的子集数目。在

def is_disjoint(disjoints, i, j, k):
    disjoints_flat = list(chain.from_iterable(disjoints))
    if (i in disjoints_flat) or (j in disjoints_flat) or (k in disjoints_flat):
        return False
    return True

.... other code 

# disjoint determination
n_disjoints = 0
disjoints = []

# sets is the input
for set in sets:
    if is_disjoint(disjoints, set[0], set[1], set[2]):
    if is_dis:
        n_disjoints += 1
        disjoints.append(set)

在获得大概值之后，我反复检查更高的可能值。为此，我尝试从给定的一组值中生成所有可能的k大小的子集（k被初始化为上面获得的数字），然后我尝试检查是否可以找到不相交的子集。如果是这样，那么我会检查k+1大小的子集。然而，我的代码在生成k可能的子集时运行得非常慢。我希望有人能提出任何加快解决方案的方法。这是暴力搜索部分的代码。在

^{pr2}$

Answer 1

可以对生成器使用递归：

all_vals = [[0, 1, 3], [0, 2, 12], [6, 9, 10], [2, 4, 11], [2, 7, 13], [3, 5, 11], [3, 7, 10], [4, 10, 14], [5, 13, 14]]

class _subsets:
   def is_disjoint(self, _vals:list) -> bool:
     _c = [i for b in _vals for i in b]
     return len(_c) == len(set(_c))
   def _combos(self, _sets, _current = []):
     if len(_current) == len(_sets) and self.is_disjoint(_current):
       yield _current
     else:
       if len(_current) > 1 and self.is_disjoint(_current):
         yield _current
       for i in _sets:
          if i not in _current:
             yield from self._combos(_sets, _current+[i]) 
   def __call__(self, _sets):
      return max(list(self._combos(_sets)), key=len)



_result = _subsets()(all_vals)
print(f'{len(_result)}: {_result}')

输出：

^{pr2}$

Answer 2

如前所述，你应该把问题归结为求最大独立集的问题，而最大独立集问题可以归结为最大团问题。在

我刚刚实现了相当快的算法，我很高兴与您分享，但我没有任何力量来解释它，因为它已经足够复杂和复杂了。你可以看一下核心思想here。在

请随意使用此代码：^{}

在您提供的示例大列表中，它适用于6 sec（0.5 sec，如果您使用的是pypy）。在

Answer 3

创建一个图，使列表是顶点，如果两个顶点不相交，则两个顶点是连接的。而你的问题是找到maximum independent set。在

在任何情况下，处理图结构都比子集和它们上的操作更简单、更快。在