30
I have a collection of unique sets (represented as bit masks) and would like to eliminate all elements that are proper subsets of another element. For example:
input = [{1, 2, 3}, {1, 2}, {2, 3}, {2, 4}, {}]
output = [{1, 2, 3}, {2, 4}]
I have not been able to find a standard algorithm for this, or even a name for this problem, so I am calling it "maximal subsets" for lack of anything else. Here is an O(n^2) algorithm (in Python for concreteness), assuming is_subset_func is O(1):1
def eliminate_subsets(a, cardinality_func, is_subset_func):
out = []
for element in sorted(a, reverse=True, key=cardinality_func):
for existing in out:
if is_subset_func(element, existing):
break
else:
out.append(element)
return out
Is there a more efficient algorithm, hopefully O(n log n) or better?
1 For bit masks of constant size, as is true in my case, is_subset_func is just element & existing == element, which runs in constant time.