Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Largest possible number of disjoint subsets in a set

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
like image 438
picotard Avatar asked Oct 31 '18 04:10

picotard


People also ask

How do I find the number of disjoint sets?

Now we have to find out the total number of subsets of the given set S, such that the subsets are unordered pairs of disjoint subsets of S. Now as we know that the total number of unordered pairs of disjoint subsets of any set containing n elements is equal to, N = $\dfrac{{{3^n} + 1}}{2}$....................

What is meant by disjoint subsets?

A pair of sets which does not have any common element are called disjoint sets. For example, set A={2,3} and set B={4,5} are disjoint sets.

Are subsets unordered?

Unordered pairs are commonly defined as subsets, as follows: If A is a set and x and y are elements of A, then the unordered pair or pair set {x,y} is the subset of A with the property that z∈{x,y} if and only if z=x or z=y. Note that {x,x}={x}, a singleton.


2 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.

like image 137
Ante Avatar answered Oct 05 '22 10:10

Ante


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]]
like image 24
Ajax1234 Avatar answered Oct 05 '22 11:10

Ajax1234