Tengo una colección de conjuntos únicos (representados como máscaras de bits) y me gustaría eliminar todos los elementos que sean subconjuntos adecuados de otro elemento. Por ejemplo:

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

No he podido encontrar un algoritmo estándar para esto, ni siquiera un nombre para este problema, así que lo llamo "subconjuntos máximos" por falta de cualquier otra cosa. Aquí hay un algoritmo O (n ^ 2) (en Python por concreción), asumiendo queis_subset_func es 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 un algoritmo más eficiente, con suerte O (n log n) o mejor?

1 Para máscaras de bits de tamaño constante, como es cierto en mi caso,is_subset_func es soloelement & existing == element, que se ejecuta en tiempo constante.