Suponha que eu tenho uma lista de subconjuntos de { 1 , . . . , n } . Eu posso fazer o pré-processamento nesta lista, se necessário. Após este pré-processamento, eu sou apresentado com um outro conjunto A ⊆ { 1 , . . . , n } . Quero identificar quaisquer conjuntos B ∈ X com B ⊆ A .
O algoritmo óbvio (sem nenhum pré-processamento) leva tempo - você simplesmente testa A contra cada B ∈ X separadamente. Existe algo melhor que isso?
Se ajudar, você pode assumir que, para qualquer , o número total de correspondências B ∈ X é limitado por algo como O ( 1 ) .
fonte
Talvez você possa usar uma técnica de "recuperação de informações": na fase de pré-processamento, crie um índice invertido (no seu caso, é suficiente uma matriz bidimensional ) que mapeia um elemento para os conjuntos em que o contêm: .n×|X| xi∈{1,...,n} X inv(xi)={Xj∈X|xi∈Xj}
Configure um array inteiro de comprimento.occ |X|
Então, para cada recupera , e para cada ocorreyi∈A inv(yi) Xj∈inv(yi) occ[j]=occ[j]+1
No final, os conjuntos necessários são aqueles para os quais .|Xj|=occ[j]
Você pode acelerar arbitrariamente o processo (ao custo do espaço exponencial) indexando dois ou mais elementos juntos.
fonte