Coleção de conjuntos que não contêm conjuntos que são um subconjunto de outro na coleção

Question

Estou procurando uma estrutura de dados abstrata que represente uma coleção de conjuntos de modo que nenhum conjunto na coleção seja um subconjunto de outro conjunto da coleção.

Isso significa que, ao inserir, as seguintes condições serão atendidas:

A. Inserir um elemento que já é um subconjunto de outro elemento retornará a coleção original.

B. Inserir um elemento que é um superconjunto de outros elementos resultará em uma coleção com o Superset adicionado e os subconjuntos removidos.

Assumindo uma ordem nos elementos do conjunto, uma árvore de prefixo pode ser usada para representar a coleção. Isso permite que a condição A seja tratada muito rapidamente (ou seja, não é necessário mais verificar a condição do que inserir o subconjunto), no entanto, a condição de atendimento B leva tempo.

Gostaria de saber se existe uma estrutura de dados que permite que B seja atendido rapidamente.

Answer 1

A abordagem trivial seria manter uma lista de conjuntos e executar uma pesquisa linear por meio de cada conjunto de entrada (testando se a entrada é um subconjunto).

Obviamente, isso é executado no tempo de O (n) para a pesquisa linear e possivelmente o tamanho (m) para o tamanho do conjunto de entrada. Assim, o (n*m) tempo total (número de conjuntos vs. tamanho de cada conjunto).

A otimização mais óbvia, é claro, é indexar em tamanhos de conjunto. Em seguida, você testará apenas cada conjunto de entrada contra aqueles que são de tamanho igual ou maior. (Um conjunto não pode ser um subconjunto de nenhum conjunto menor, duh!).

A próxima otimização que vem à mente é criar no índice de elementos. Assim, para cada conjunto de entrada, você encontraria a interseção de cada conjunto que contém cada um dos elementos. Em outras palavras, se, para o conjunto de entrada {a, b, c}, descobrimos que o elemento {a} existe nos conjuntos a, b e d, elemento {b} existe em b, e e f e {c} Existe em A, B e Z ... então o conjunto de entrada é um subconjunto de B (a interseção de {a, b, d}, {b, e, f} e {a, b, z}).

Então, isso soa como O (M*log (n)) complexidade para mim. (Temos que executar pesquisas hashed em cada elemento de cada conjunto de entrada). As inserções também devem estar na mesma ordem (inserindo o ID do novo conjunto em cada um dos mapas do elemento). (Na análise BIG-O 2*O (Mlog (n)) reduz para O (Mlog (n)), é claro).

Answer 2

Uma idéia trivial, que funcionará em O (k), onde K tem o tamanho do elemento que está sendo adicionado.

• Mantenha os conjuntos da maneira que quiser
• Mantenha o mapa de set_id -> set_size
• Mantenha o mapa do objeto -> set_id

Ambos A e B são O (K).

Answer 3

Se os membros individuais de seus conjuntos A, B, ... forem mapeados para números primos distintos (e relativamente) e, ao lado de cada conjunto, você armazena o produto de todos os membros como P (a), P (B) etc. Então, então Subconjuntos e superconjuntos podem ser encontrados se p (x) é um fator de p (y) ou vice -versa.

Acho que você pode acabar com alguns números muito grandes, mas funciona em teoria.

Por exemplo:

Se [ABCD] -> [2 3 5 7], P (ABC) = 30, P (ABD) = 42, P (BC) = 15, P (ABCD) = 210

Answer 4

Que site idiota! Agora me registrei, então, no devido tempo, pode comentar sobre coisas de ontem. Até então, no entanto ...

@Stephen C: Embora eu acredite que meu inglês seja adequado, pareço ter adquirido um explicador: ele perdeu bits, no entanto, e seu comentário deve ler o seguinte:

---

@Stephen C: Encontrar os fatores de um número arbitrário é de fato NP completo, mas não relevante aqui. A questão é se os menores de dois números dividem exatamente quanto maior, uma operação simples do módulo. Por exemplo, P (BC) = 15 é um divisor de P (ABCD) = 210, então BC é um subconjunto de ABCD (como os conjuntos ABD e ABC).

A adição de um novo conjunto S à coleção existente de N Sets é O (n), assumindo que a comparação e a divisão dos grandes números levam aproximadamente ao mesmo tempo, independentemente do N.

Para cada entrada existente e na coleção de conjuntos, pare se p (s) <p (e) e p (s) dividirem p (e) exatamente. Se p (s) = P (e), pare. Remova e se p (s)> p (e) e p (e) divide exatamente p (s). Adicione s se você chegar ao final da coleção. Uma variedade de bignums funcionaria.

---

@JL: Se você quiser ser meu perseguidor no local, por favor, aproveite-se a 1) Adicione o valor 2) com precisão.