CODEWITHSUNDEEP
c++algorithmdata-structuresset
aceBox
aceBox

Reputation: 731

What can be the algorithm to find all disjoint sets from a set of sets?

I have 'n' sets (n<10). Each set may have lets say, 1000 elements. I want to find all the disjoint sets for these sets. Say, for eg, I have sets 

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

Then the output would be {{5}, {2,6}, {1}, {7}}. What can be the algorithm for this? I thought about finding pairwise disjoint sets and then using these new (disjoint)sets to again find disjoint sets from the sets which are left. But this will not scale well. Hope this helps: Diagram Example

Upvotes: 7

Views: 1745

Answers (1)

88877
88877

Reputation: 495

You can consider your problem as a boolean two entry map, elements being the rows, sets being the columns and the boolean is the answer of the question is the element included in the set. For instance your example would be:

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

Then create a key for each element describing the differents sets it is in and register this element in a map.

For instance if we consider the key creation function as something like this:

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

We can then create the map:

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

and return the elements of this map.

Upvotes: 3

Related Questions