У меня есть коллекция уникальных наборов (представленных в виде битовых масок), и я хотел бы удалить все элементы, которые являются правильными подмножествами другого элемента. Например:

input = [{1, 2, 3}, {1, 2}, {2, 3}, {2, 4}, {}]
output = [{1, 2, 3}, {2, 4}]

Мне не удалось найти стандартный алгоритм для этого или даже название для этой проблемы, поэтому я называю это "максимальные подмножества из-за отсутствия чего-либо еще. Вот алгоритм O (n ^ 2) (для конкретности в Python), предполагаяis_subset_func О (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

Есть ли более эффективный алгоритм, надеюсь, O (n log n) или лучше? 1

 Для битовых масок постоянного размера, как это верно в моем случае,is_subset_func простоelement & existing == element, который работает в постоянном времени.