Algorithmus zum Finden eines isomorphen Satzes von Permutationen

Ich habe eine Reihe von Permutationen und möchte isomorphe Permutationen entfernen.

Wir haben S Sätze von Permutationen, wobei jeder Satz enthält K Permutationen, und jede Permutation wird als und Array von dargestellt N Elemente. Ich speichere es gerade als Array int pset[S][K][N]wo S, K und N fest sind und N größer als K ist.

Zwei Sätze von Permutationen, A und Bsind isomorphwenn es eine Permutation gibt Pdas Elemente aus konvertiert A zu B (z.B. wenn a ist ein Element der Menge Adann P(a) ist ein Element der Menge B). In diesem Fall können wir das sagen P macht A und B isomorph.

Mein aktueller Algorithmus ist:

1. Wir wählen alle Paare aus s1 = pset[i] und s2 = pset[j]so dass i < j
2. Jedes Element aus ausgewählten Sets (s1 und s2) werden von nummeriert 1 zu K. Das bedeutet, dass jedes Element dargestellt werden kann als s1[i] oder s2[i]wo 0 < i < K+1
3. Für jede Permutation T von K Elemente machen wir folgendes:
   • Finden Sie die Permutation Rso dass R(s1[1]) = s2[1]
   • Überprüfen Sie, ob R ist eine Permutation, die machen s1 und T(s2) isomorph, wo T(s2) ist eine Neuanordnung der Elemente (Permutationen) der Menge s2also prüfen wir im Grunde nur, ob R(s1[i]) = s2[T[i]]wo 0 < i < K+1
   • Wenn nicht, gehen wir zur nächsten Permutation T.

Dieser Algorithmus arbeitet sehr langsam: O(S^2) für den ersten Schritt, O(K!) um jede Permutation zu durchlaufen T, O(N^2) die zu finden Rund O(K*N) zu prüfen, ob die R ist die Permutation, die macht s1 und s2 isomorph – so ist es O(S^2 * K! * N^2).

Frage: Können wir es schneller machen?

Sie können sortieren und vergleichen:

// 1 - sort each set of permutation
for i = 0 to S-1
    sort(pset[i])
// 2 - sort the array of permutations itself
sort(pset)
// 3 - compare
for i = 1 to S-1 {
    if(areEqual(pset[i], pset[i-1]))
        // pset[i] and pset[i-1] are isomorphic
}

Ein konkretes Beispiel:

0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]

Nach 1:

0: [[1,2,3],[3,2,1]]
1: [[1,3,2],[2,3,1]] // order changed
2: [[1,2,3],[2,3,1]]
3: [[1,2,3],[3,2,1]] // order changed

Nach 2:

2: [[1,2,3],[2,3,1]]
0: [[1,2,3],[3,2,1]]
3: [[1,2,3],[3,2,1]] 
1: [[1,3,2],[2,3,1]]

Nach 3:

(2, 0) not isomorphic 
(0, 3) isomorphic
(3, 1) not isomorphic

Was ist mit der Komplexität?

• 1 ist O(S * (K * N) * log(K * N))
• 2 ist O(S * K * N * log(S * K * N))
• 3 ist O(S * K * N)

Die Gesamtkomplexität ist also O(S * K * N log(S * K * N))

Dafür gibt es eine ganz einfache Lösung: Transposition.

Wenn zwei Mengen isomorph sind, bedeutet dies, dass eine Eins-zu-Eins-Abbildung existiert, bei der die Menge aller Zahlen am Index steht i im Satz S1 ist gleich der Menge aller Zahlen an einem Index k im Satz S2. Meine Vermutung ist, dass keine zwei nicht isomorphen Mengen diese Eigenschaft haben.

(1) Beispiel von Jean Logeart:

0: [[1,2,3],[3,2,1]]
1: [[2,3,1],[1,3,2]]
2: [[1,2,3],[2,3,1]]
3: [[3,2,1],[1,2,3]]

Perform ONE pass:

Transpose, O(n):
0: [[1,3],[2,2],[3,1]]

Sort both in and between groups, O(something log something):
0: [[1,3],[1,3],[2,2]]

Hash:
"131322" -> 0

...
"121233" -> 1
"121323" -> 2
"131322" -> already hashed.

0 and 3 are isomorphic.

(2) Gegenbeispiel von vsoftco in seinem Kommentar zu Jean Logearts Antwort:

A = [ [0, 1, 2], [2, 0, 1] ]
B = [ [1, 0, 2], [0, 2, 1] ]

"010212" -> A
"010212" -> already hashed.

A and B are isomorphic.

Sie können jeden Satz in eine transponierte sortierte Zeichenfolge oder einen Hash oder ein beliebiges komprimiertes Objekt für einen linearen Zeitvergleich umwandeln. Beachten Sie, dass dieser Algorithmus alle drei Sätze berücksichtigt A, B und C als isomorph, selbst wenn man p konvertiert A zu B und ein anderer p konvertiert A zu C. Offensichtlich gibt es in diesem Fall ps jeden dieser drei Sätze in den anderen umzuwandeln, da wir nur jeden verschieben müssen i in einem Satz zu einem bestimmten k in dem anderen. Wenn, wie Sie sagten, Ihr Ziel darin besteht, “isomorphe Permutationen zu entfernen”, erhalten Sie dennoch eine Liste der zu entfernenden Sätze.

Erläuterung:

Angenommen, wir haben zusammen mit unserem sortierten Hash aufgezeichnet, welche Permutation jeweils vorliegt i kam aus. Gegenbeispiel von vsoftco:

010212  // hash for A and B
100110  // origin permutation, set A
100110  // origin permutation, set B

Um die Isomorphie zu bestätigen, müssen wir zeigen, dass die i‘s gruppiert in jedem Index ab dem ersten verschobenen Satz etwas Index im zweiten Satz, welcher Index keine Rolle spielt. Sortieren der Gruppen von i‘s macht die Lösung nicht ungültig, sondern dient dazu, die Bewegung/Permutation zwischen Sätzen zu bestätigen.

Nun per Definition jede Zahl in einem Hash und jede Zahl in jeder Gruppe im Hash in einer Ursprungspermutation genau einmal für jeden Satz vertreten ist. Wir entscheiden uns jedoch dafür, die Zahlen in jeder Gruppe von anzuordnen iim Hash ist, ist uns garantiert, dass jede Zahl in dieser Gruppe eine andere Permutation in der Menge darstellt; und in dem Moment, in dem wir diese Nummer theoretisch zuweisen, ist uns garantiert, dass sie nur für diese Permutation und diesen Index “reserviert” ist. Sagen wir für eine bestimmte Zahl 2in den beiden Hashes ist uns garantiert, dass es aus einem Index und einer Permutation im Satz stammt Aund im zweiten Hash entspricht einem Index und einer Permutation im Satz B. Das ist alles, was wir wirklich zeigen müssen – dass die Zahl in einem Index für jede Permutation in einer Menge (einer Gruppe von eindeutigen i‘s) ging zu nur ein Index in der anderen Menge (eine Gruppe von distinkten k‘s). Zu welcher Permutation und welchem ​​Index die Zahl gehört, ist unerheblich.

Denken Sie daran, dass jeder Satz S2isomorph zu set S1daraus abgeleitet werden können S1 Verwenden einer Permutationsfunktion oder verschiedener Kombinationen unterschiedlicher angewandter Permutationsfunktionen S1‘s Mitglieder. Was das Sortieren oder Neuordnen unserer Zahlen und Gruppen tatsächlich darstellt, ist die Permutation, die wir als Lösung für den Isomorphismus zuweisen, und nicht eine tatsächliche Zuordnung, welche Zahl aus welchem ​​​​Index und welcher Permutation stammt. Hier ist wieder das Gegenbeispiel von vsoftco, dieses Mal werden wir die Ursprungsindizes unserer Hashes hinzufügen:

110022 // origin index set A
001122 // origin index set B

Deshalb unsere Permutationeine Lösung des Isomorphismus, ist:

Oder der Reihe nach:

(Beachten Sie, dass es in Jean Logearts Beispiel mehr als eine Lösung für den Isomorphismus gibt.)

Angenommen, zwei Elemente von s1, s2 \in S sind isomorph. Dann wenn p1 und p2 sind also Permutationen s1 ist isomorph zu s2 iff p1(s1) ist isomorph zu p2(s2) wo pi (si) ist der Satz von Permutationen, der durch Anwendung erhalten wird Pi zu jedem Element in si.

Für jeden ich in 1 … s und j in 1…kwählen Sie das j-th Mitglied von si, und finden Sie die Permutation, die es in Eins ändert. Wenden Sie es auf alle Elemente von an si. Hash jedes der k Permutationen zu einer Zahl, Erhalten k Zahlen, für jede Wahl von ich und jnach Aufwand nk.

Vergleichen der gehashten Sätze für zwei verschiedene Werte von ich und j ist k^2 . So können Sie den Satz von Kandidatenübereinstimmungen zum Selbstkostenpreis finden s^2 k^3 n. Wenn die tatsächliche Anzahl der Übereinstimmungen gering ist, liegt die Gesamtkomplexität weit unter dem, was Sie in Ihrer Frage angegeben haben.