Comparando coleções de subconjuntos até permutação

Question

I têm uma matriz de uma [i] [j]. Os elementos são char, interpretado como subconjuntos do conjunto {1, ..., 8} (o elemento k é no subconjunto se o k-ésimo bit é 1). Eu não acho que é relevante, mas cada elemento tem exatamente 4 bits set.

Cada linha a [1] [j] .. a [n] [j] é uma coleção de subconjuntos de {1, ..., 8}. Eu preciso remover as linhas duplicadas, onde duas linhas são consideradas duplicatas se um pode ser obtido a partir do outro por uma permutação de {1, ..., 8}.

Exemplo (número 0bxxxxxxxx meios binário):

0b11000000, 0b01100000, 0b00110000

é uma duplicata de

0b00110000, 0b00011000, 0b00100100

porque o primeiro pode ser obtido a partir do último por aplicação da permutação

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6

e reordenar o resultado.

Para considerações de desempenho, a matriz cont cerca de 2000 linhas, cada uma compreendendo, no máximo, 20 elementos. Cada linha já está ordenado, e também as linhas estão em ordem crescente lexicográfica, se isso pode ajudar. O resto do algoritmo é escrito em C, de modo que uma solução de C seria preferida.

Obrigado por sua ajuda.

Answer 1

Se todos os subconjuntos tinha 2 elementos, isso representaria gráfico isomorfismo , com os subconjuntos representando os bordos do gráfico. Isto é ainda mais geral (assim, provavelmente mais difícil), então eu olhar para heurísticas usadas para resolver gráfico isomorfismo e ver se elas se aplicam aqui.

Há uma série de heurísticas gráfico-isomorfismo que pode mais barato excluem isomorfismo. Para uma coleção particular, você pode calcular quantos subconjuntos faz cada elemento pertence, em seguida, classificar isso. No seu exemplo, ambas as coleções iria ficar [2,2,1,1,0,0,0,0]. Se as seqüências ordenadas para duas coleções são diferentes, então não há isomorfismo. Da igualdade curso não garante que existe.

Existem muitas heurísticas mais semelhantes que são ainda melhor em peneirar fora gráficos não-isomórficas (e poderia se aplicam aqui).

Além disso, 8! só é 40320, então brute-forcing todas as permutações não é totalmente inviável.