En comparant les collections de sous-ensembles jusqu'à permutation

Question

I ai un tableau a [i] [j]. Les éléments sont char, interprétées comme des sous-ensembles de l'ensemble {1, ..., 8} (k élément se trouve dans le sous-ensemble si le bit de k-ième est 1). Je ne pense pas que ce soit pertinent, mais chaque élément a exactement 4 bits définis.

Chaque ligne a [1] [j] .. a [n] [j] est une collection de sous-ensembles de {1, ..., 8}. Je dois supprimer des lignes en double, où deux lignes sont considérées comme des doublons si l'on peut obtenir de l'autre par une permutation de {1, ..., 8}.

Exemple (0bxxxxxxxx moyen de nombre binaire):

0b11000000, 0b01100000, 0b00110000

est un double de

0b00110000, 0b00011000, 0b00100100

parce que la première peut être obtenue à partir de celle-ci en appliquant la permutation

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

et en réorganisant le résultat.

Pour des raisons de performance, la matrice contient environ 2 000 lignes comportant chacune au plus 20 éléments. Chaque ligne est déjà commandé, et aussi les lignes sont en ordre croissant lexicographique, si cela peut aider. Le reste de l'algorithme est écrit en C, donc une solution C serait préférable.

Merci pour votre aide.

Answer 1

Si tous les sous-ensembles ont 2 éléments, cela représenterait graphique isomorphisme, avec les sous-ensembles représentant des bords du graphe. Cela est encore plus générale (donc probablement plus difficile), donc je regarderais heuristiques utilisées pour résoudre isomorphisme graphe et voir si elles sont applicables ici.

Il y a beaucoup d'heuristiques graphique -isomorphisme qui peut exclure bon marché isomorphisme. Pour une collection particulière, vous pouvez calculer le nombre de sous-ensembles chaque élément n'appartiennent, puis trier cela. Dans votre exemple, les deux collections obtiendraient [2,2,1,1,0,0,0,0]. Si les séquences triées pour deux collections sont différentes, il n'y a pas isomorphisme. Bien sûr, l'égalité ne garantit pas qu'il existe.

Il y a beaucoup de heuristiques similaires qui sont encore mieux à tamiser des graphes non-isomorphes (et pourrait éventuellement appliquer ici).

En outre, 8! est seulement 40320, alors brute-forcer toutes les permutations ne sont pas tout à fait impossible.