title: Largest possible number of disjoint subsets in a set
body: <p>I'm given a set of lists, for instance:</p>
  
  <p><code>[[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]]</code></p>
  
  <p>I need to find the maximum number of disjoint subsets that this list contains. In this case, the answer is <code>4</code>.</p>
  
  <p>Another example is the list: 
  <code>[[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]]</code>
  Here, the answer is 8.</p>
  
  <p>I know this problem is NP-hard, so I came up with a semi brute-force way of doing this.</p>
  
  <p>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. </p>
  
  <pre><code>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)
  </code></pre>
  
  <p>After obtaining the ballpark, I iteratively check higher possible values. To do this, I try to generate all possible <code>k</code> sized subsets from the given set of values (<code>k</code> 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 <code>k+1</code> sized subsets. However, my code runs ridiculously slow while generating the <code>k</code> 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.</p>
  
  <pre><code>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 &lt;= 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
  </code></pre>