Largest possible number of disjoint subsets in a set

user_7868376 0
Viewed 1178

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
set algorithm python
3 Answers

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.

user_4940760

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

As mentioned before, you should reduce your problem to finding of maximum independent set, which you can reduce to maximum clique problem.

I've just implemented reasonably fast algorithm and I'm pleased to share it with you, but I don't have any strength left to explain it, because it's enough complicated and sophisticated. You can take a peek at core idea here.

Feel free to use this code: https://gist.github.com/mingaleg/e1872483d0d0618fe1acacccbf741050

On the big list you provided as example it works for 6 sec (0.5 sec if you are using pypy).

user_26644960
Related