Vergleicht man Sammlungen von Untergruppen bis Permutation

Question

Ich habe ein Array a [i] [j]. Die Elemente sind char, interpretiert als Teilmengen der Menge {1, ..., 8} (das Element k ist in der Teilmenge, wenn das k-te Bit ist 1). Ich glaube nicht, es ist relevant, aber jedes Element hat genau 4 Bits gesetzt.

Jede Zeile a [1] [j] .. a [n] [j] ist eine Sammlung von Teilmengen von {1, ..., 8}. Ich brauche doppelte Zeilen zu entfernen, in denen zwei Reihen Duplikate angesehen, wenn ein von dem anderen durch eine Permutation der erhalten werden kann, {1, ..., 8}.

Beispiel (0bxxxxxxxx bedeutet Binärzahl):

0b11000000, 0b01100000, 0b00110000

ist ein Duplikat

0b00110000, 0b00011000, 0b00100100

, weil die erstere von den letzteren erhalten werden, indem die Permutation Anwendung

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

und Neuordnen das Ergebnis.

Für Leistungsinformationen enthält das Array etwa 2000 Zeilen, die jeweils höchstens 20 Elemente. Jede Reihe ist bereits bestellt, und auch die Reihen in lexicographic teigender Reihenfolge, wenn diese helfen könnte. Der Rest des Algorithmus ist in C geschrieben, so dass eine C-Lösung bevorzugt würde.

Danke für Ihre Hilfe.

Answer 1

Wenn alle Teilmengen 2 Elemente hätte, würde dies bedeuten Graphisomorphie , mit den Untergruppen darstellt Graphkanten. Dies ist umso allgemeinen (also wahrscheinlich härter), so dass ich auf Heuristiken aussehen würde verwendet Graphisomorphie zu lösen und sehen, ob sie hier gelten.

Es gibt eine Menge von Graph-Isomorphismus Heuristik, die billig Isomorphismus ausschließen. Für eine bestimmte Sammlung, können Sie berechnen, wie viele Untergruppen hat jedes Element gehört, dann ist das sortieren. In Ihrem Beispiel würde sich beide Sammlungen [2,2,1,1,0,0,0,0]. Wenn die sortierten Sequenzen für zwei Sammlungen unterschiedlich sind, dann gibt es keinen Isomorphismus. Gleichheit garantiert natürlich nicht, dass es ist.

Es gibt viele weitere ähnliche Heuristik, die noch besser ist Aussieben nicht-isomorphe Graphen (und könnte möglicherweise gelten hier).

Auch 8! ist nur 40.320, so Permutationen Brute-Forcing alle nicht völlig undurchführbar.