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
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}$....................
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.
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.
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.
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]]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With