Largest possible number of disjoint subsets in a set

Question

I'm given a set of lists, for instance:

[[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]]

I need to find the maximum number of disjoint subsets that this list contains. In this case, the answer is 4.

Another example is the list: [[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]] Here, the answer is 8.

I know this problem is NP-hard, so I came up with a semi brute-force way of doing this.

I first get an approximate answer by adding subsets to a list of disjoint subsets. So, whenever I iterate through a set, I check if it is already present in the disjoint subset list. If it isn't, I add it to the list. This gives me a ballpark figure that may or may not be the maximum possible number of subsets.

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)

After obtaining the ballpark, I iteratively check higher possible values. To do this, I try to generate all possible k sized subsets from the given set of values (k is initialized to the number obtained above), and then I try to check whether I can find a subset that is disjoint. If I do, then I check for k+1 sized subsets. However, my code runs ridiculously slow while generating the k possible subsets. I was hoping someone could suggest any way to speed up the solution. Here's the code for the brute force search part.

def is_subset_disjoint(subset):
    disjoints = []
    n_disjoints = 0
    for set in subset:
        if is_disjoint(disjoints, set[0], set[1], set[2]):
            disjoints.append(set)
            n_disjoints += 1

    if n_disjoints == len(subset):
        return True
    return False

..... other code 

curr = n_disjoints+1
while n_disjoints <= n_sets:
    all_possible_subsets = [list(i) for i in combinations(sets, curr)] # This runs really really slowly (makes sense since exponential for large values)
    for subset in all_possible_subsets:
        if is_subset_disjoint(subset):
            n_disjoints += 1
            curr += 1
            continue
    break

Answer 1

Create a graph so that lists are vertices and two vertices are connected if they are not disjoint. Than your problem is to find maximum independent set.

In any case it is simpler and faster to work with graph structure than subsets and operations on them.

Answer 2

You can use recursion with a generator:

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}')

Output:

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