从一组集合中找到所有不相交集合的算法是什么？

Question

我有 'n' 组 (n<10)。每组可能有 1000 个元素。我想找到这些集合的所有不相交集合。例如，我有集合

A = {2,5,6,7}, B = {5,1} and C = {5,7}. 

那么输出将是{{5}, {2,6}, {1}, {7}}。这可以是什么算法？我考虑过找到成对的不相交集，然后使用这些新的（不相交的）集再次从剩下的集合中找到不相交的集。但这不会很好地扩展。希望这会有所帮助：Diagram Example

Answer 1

您可以将您的问题视为布尔值两项映射，元素是行，集合是列，布尔值是问题的答案是集合中包含的元素。例如你的例子是：

t A B C
2 1 0 0
5 1 1 1
6 1 0 0
7 1 0 1 
1 0 1 0

然后为描述它所在的不同集合的每个元素创建一个键，并在映射中注册该元素。

例如，如果我们认为密钥创建函数是这样的：

int keyFunction(bool Xa, bool Xb, bool Xc) {
  int key =0;
  if (Xa) {key+=4;}
  if (Xb) {key+=2;}
  if (Xc) {key+=1;}
  return key;
}

然后我们可以创建地图：

Key ElementsQueue
0   []
1   []
2   [1]
3   []
4   [2,6]
5   [7]
6   []
7   [5]

和return这张地图的元素。