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

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

您可以将您的问题视为一个 bool 值二项映射，元素是行，集合是列， bool 值是问题的答案是集合中包含的元素。例如你的例子是:

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

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

例如，如果我们认为 key 创建函数是这样的:

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;
}

然后我们可以创建 map :

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

并返回这张 map 的元素。