Vergleichen Sammlungen von Subsets 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 1 ist). Ich denke nicht, dass es relevant ist, 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 muss doppelte Zeilen entfernen, wobei zwei Zeilen als Duplikate betrachtet werden, wenn man durch eine Permutation von {1, ..., 8} von der anderen erhalten werden kann.

Beispiel (0bxxxxxxxx bedeutet Binärzahl):

0b11000000, 0b01100000, 0b00110000 

ist ein Duplikat

0b00110000, 0b00011000, 0b00100100 

weil erstere durch Anwenden der Permutation von diesem erhalten werden kann

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

und das Ergebnis neu ordnen.

Aus Leistungsgründen enthält das Array etwa 2000 Zeilen mit jeweils maximal 20 Elementen. Jede Zeile ist bereits geordnet, und auch die Zeilen sind in lexikographischer Reihenfolge angeordnet, falls dies helfen könnte. Der Rest des Algorithmus ist in C geschrieben, daher wäre eine C-Lösung bevorzugt.

Danke für Ihre Hilfe.

Answer 1

Wenn alle Teilmengen 2 Elemente hätten, würde dies graph isomorphism darstellen, wobei die Teilmengen Graphkanten darstellen. Dies ist noch allgemeiner (also wahrscheinlich härter), also würde ich Heuristiken betrachten, die verwendet werden, um den Graphisomorphismus zu lösen und zu sehen, ob sie hier zutreffen.

Es gibt viele Graph-Isomorphie Heuristiken, die Isomorphismus billig ausschließen können. Für eine bestimmte Sammlung können Sie berechnen, wie viele Teilmengen jedes Element angehört, und dann sortieren. In Ihrem Beispiel würden beide Sammlungen [2,2,1,1,0,0,0,0] erhalten. Wenn die sortierten Sequenzen für zwei Sammlungen unterschiedlich sind, dann gibt es keinen Isomorphismus. Natürlich garantiert die Gleichheit das nicht.

Es gibt viele weitere ähnliche Heuristiken, die noch besser beim Aussieben von nicht isomorphen Graphen sind (und möglicherweise hier angewendet werden könnten).

Auch 8! ist nur 40320, also ist das brutale Erzwingen aller Permutationen nicht völlig undurchführbar.