União / intersecção de 2 conjuntos, onde cada conjunto são definidos por ele é subconjuntos

Question

Sabemos definição de cada conjunto da união de outros conjuntos.

Por exemplo

A = B union {1,2}

B = C união D

= C {5,6}

= D {5,7}

E = {4}

então A = {1,2,5,6,7}

A união E = {1,2,4,5,6,7}

Os quaisquer algoritmos eficientes de fazer isso. Suponha que a hierarquia dos sindicatos pode ser muito profundo, e os subconjuntos pode mudar muito frequentemente (não muito). Eu acho que deveria haver formas de minimizar reduzir a quantidade de uniões um tem que fazer.

Answer 1

Então você tem uma hierarquia imutável de sindicatos de mudar sets? E você está, como no seu exemplo, interessado apenas no valor de um conjunto?

Em seguida, achatar a hierarquia. Isto é, no seu exemplo você uma vez percorrer a hierarquia para encontrar o conjunto de mudar conjuntos seu conjunto é a união de, e armazenar este conjunto.

dispense Para com os sindicatos recomputing sempre que um conjunto de folha alterações, você poderia seguir para cada elemento em quantos jogos ele está contido. Isso pode ser atualizado rapidamente se um conjunto folha muda, e os que não necessário olhar para todos os conjuntos de folhas inalteradas. Então, esses elementos com contagem de frequência> 0 Atualmente na União.

Answer 2

Talvez você está procurando algum tipo de disjuntos set estrutura de dados

Answer 3

Várias perguntas sobre este caso.

Primeira pergunta: Por quanto tempo é que isto "script" / "programa" tem que correr? No caso, não é muito longo, ele poderia muito bem ser uma boa opção de simplesmente armazenar uniões anteriores e cache de verificação antes de executar uma ação sindical. A memória não é tão caro hoje em dia:.)

Segundo pergunta que você deve perguntar: são elementos em uma certa ordem antes da união? Se eles não são, e uma lista é acessado mais de uma vez, pode ser muito útil para classificar uma lista primeiro (que você pode tomar uma decisão quando você está apenas na metade de uma lista, por exemplo). Mergesort é uma técnica poderosa do eficiente junção de duas listas ordenadas.