Eu tenho uma coleção de conjuntos exclusivos (representados como máscaras de bits) e gostaria de eliminar todos os elementos que são subconjuntos adequados de outro elemento. Por exemplo:

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

Eu não consegui encontrar um algoritmo padrão para isso, ou mesmo um nome para esse problema, então estou chamando de "subconjuntos máximos" por falta de qualquer outra coisa. Aqui está um algoritmo O (n ^ 2) (em Python para concretude), assumindois_subset_func é 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

Existe um algoritmo mais eficiente, esperançosamente O (n log n) ou melhor?

1 Para máscaras de bit de tamanho constante, como é verdade no meu caso,is_subset_func é apenaselement & existing == element, que é executado em tempo constante.