Gruppen
In der abstrakten Algebra ist eine Gruppe ein Tupel , wobei eine Menge und eine Funktion so dass gilt:
Für alle in ist .G ( x ≤ y ) ≤ z = x ≤ ( y ≤ z )
Es gibt ein Element in so dass für alle in , .G x G x ∗ e = x
Für jedes in existiert ein Element in so dass .G y G x ∗ y = e
Die Ordnung einer Gruppe wird als die Anzahl von Elementen von definierten .G
Für jede streng positive ganze Zahl existiert mindestens eine Gruppe der Ordnung . Zum Beispiel ist eine solche Gruppe, wobei und x + _ny = (x + y) \ modn .n ( C n , + n ) C n = { 0 , . . . , n - 1 } x + n y = ( x + y )
Isomorphe Gruppen
Sei und definiere durch . Dann ist und .
Ebenso ist und .
Obwohl die Elemente und Operationen der Gruppen und unterschiedliche Namen haben, haben die Gruppen dieselbe Struktur.
Zwei Gruppen und gelten als isomorph, wenn eine Bijektion so dass für alle in .
Nicht alle Gruppen derselben Ordnung sind isomorph. Zum Beispiel ist die Klein-Gruppe eine Gruppe der Ordnung 4, die nicht isomorph zu .
Aufgabe
Schreiben Sie ein Programm oder eine Funktion, die eine nicht negative Ganzzahl n als Eingabe akzeptiert und die Anzahl der nicht isomorphen Gruppen der Ordnung n ausgibt oder zurückgibt .
Testfälle
Input Output
0 0
1 1
2 1
3 1
4 2
5 1
6 2
7 1
8 5
9 2
10 2
11 1
12 5
13 1
14 2
15 1
16 14
17 1
18 5
19 1
20 5
(entnommen aus OEIS A000001 )
Zusätzliche Regeln
Die Ausführungszeit und die Speichernutzung sind nicht begrenzt.
Built-Ins, die diese Aufgabe banalisieren, wie Mathematics
FiniteGroupCount
, sind nicht zulässig.Es gelten die Standardregeln für Code-Golf .
quelle
monkeys_on_typewriters
Buildin deckt alles ab, was nicht in den dokumentierten Buildins enthalten ist.Antworten:
CJam,
189187 BytesDas wird schwer zu erklären sein ... Zeitkomplexität ist garantiert
O(scary)
.Wenn Sie mutig genug sind, versuchen Sie es online . Auf meinem beschissenen Laptop kann ich bis zu 6 mit dem Java-Interpreter oder 5 mit dem Online-Interpreter bekommen.
Erläuterung
Ich habe keinen großen mathematischen Hintergrund (bin gerade mit dem Abitur fertig, fange nächste Woche an der Uni an). Nehmen Sie es also mit, wenn ich Fehler mache, das Offensichtliche erkläre oder Dinge auf schrecklich ineffiziente Weise tue.
Mein Ansatz ist eine rohe Kraft, obwohl ich versucht habe, ihn etwas schlauer zu machen. Die Hauptschritte sind:
Bevor Sie sich ansehen, wie die einzelnen Schritte ausgeführt werden, sollten Sie zunächst einen einfachen Code aus dem Weg räumen:
Der folgende Algorithmus funktioniert mit n <4 nicht richtig , die Fälle von 0 bis 3 werden mit einer doppelten Negation behandelt.
Von nun an werden die Elemente einer Gruppe als {1, a, b, c, ...} geschrieben , wobei 1 das Identitätselement ist. In der CJam-Implementierung sind die entsprechenden Elemente {0, 1, 2, 3, ...} , wobei 0 das Identitätselement ist.
Beginnen wir mit Schritt 1. Das Schreiben aller möglichen Operatoren für eine Gruppe der Ordnung n entspricht dem Generieren aller gültigen n × n Cayley-Tabellen . Die erste Zeile und Spalte sind trivial: Sie sind beide {1, a, b, c, ...} (von links nach rechts, von oben nach unten).
Wenn Sie wissen, dass eine Cayley-Tabelle auch ein reduziertes lateinisches Quadrat ist (aufgrund der Löschungseigenschaft), können Sie die möglichen Tabellen zeilenweise generieren. Ausgehend von der zweiten Zeile (Index 1) generieren wir alle eindeutigen Permutationen für diese Zeile, wobei die erste Spalte auf den Wert des Index festgelegt bleibt.
Natürlich sind nicht alle diese Permutationen gültig: Jede Zeile und Spalte muss genau einmal alle Elemente enthalten. Zu diesem Zweck wird ein Filterblock verwendet (ein wahrer Wert behält die Permutation bei, ein falscher entfernt sie):
Beachten Sie, dass ich innerhalb der Generierungsschleife filtere: Dadurch wird der Code etwas länger (im Vergleich zu einer eindeutigen Generierung und Filterung), aber die Leistung wird erheblich verbessert. Die Anzahl der Permutationen einer Menge der Größe n ist n! Daher würde die kürzere Lösung viel Speicher und Zeit erfordern.
Eine Liste gültiger Cayley-Tabellen ist ein guter Schritt, um die Operatoren aufzulisten. Da es sich jedoch um eine 2D-Struktur handelt, kann die Assoziativität nicht überprüft werden, da es sich um eine 3D-Eigenschaft handelt. Der nächste Schritt ist das Herausfiltern von nicht assoziativen Funktionen.
Puh! Viel Arbeit, aber jetzt haben wir alle Gruppen der Ordnung n (oder besser die Operationen darauf - aber die Menge ist fest, so ist es das gleiche) aufgezählt . Nächster Schritt: Finden Sie Isomorphismen. Ein Isomorphismus ist eine Bijektion zwischen zwei dieser Gruppen, so dass φ (x ∗ y) = φ (x) ∗ φ (y) . Das Erzeugen dieser Bijektionen in CJam ist trivial:
Ne!
wird es tun. Wie können wir sie überprüfen? Meine Lösung geht von zwei Kopien der Cayley-Tabelle für x ∗ y aus . Bei einer Kopie wird φ auf alle Elemente angewendet, ohne die Reihenfolge der Zeilen oder Spalten zu berühren. Dies erzeugt die Tabelle für φ (x ∗ y) . Auf der anderen Seite bleiben die Elemente unverändert, aber Zeilen und Spalten werden durch φ abgebildet . Das heißt, die Zeile / Spaltex wird zur Zeile / Spalte φ (x) . Dies erzeugt die Tabelle für φ (x) ∗ φ (y) . Nachdem wir nun die beiden Tabellen haben, müssen wir sie nur vergleichen: Wenn sie gleich sind, haben wir einen Isomorphismus gefunden.Natürlich müssen wir auch die Gruppenpaare erzeugen, an denen der Isomorphismus getestet werden soll. Wir brauchen alle 2-Kombinationen der Gruppen. Sieht so aus, als hätte CJam keinen Operator für Kombinationen. Wir können sie generieren, indem wir jede Gruppe nur mit den darauf folgenden Elementen in der Liste kombinieren. Unterhaltsame Tatsache: Die Anzahl der 2-Kombinationen ist n × (n - 1) / 2 , was auch die Summe der ersten n - 1 natürlichen Zahlen ist. Solche Zahlen werden Dreieckszahlen genannt: Probieren Sie den Algorithmus auf Papier aus, eine Zeile pro festes Element, und Sie werden sehen, warum.
Der obige Code behebt das erste Element des Paares, L [X] , und kombiniert es mit anderen Gruppen (nennen wir jedes dieser Y ). Es übergibt das Paar an einen Isomorphismus-Testblock, den ich gleich zeigen werde. Der Block gibt eine Liste von Werten von zurück Y zurück, für die L [X] isomorph zu Y ist . Dann wird L [X] an diese Liste angehängt. Bevor wir verstehen, warum die Listen so aufgebaut sind, schauen wir uns den Isomorphismustest an:
Großartig, jetzt haben wir eine Liste von Mengen wie [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . Die Idee dabei ist, dass nach transitiver Eigenschaft, wenn zwei Mengen mindestens ein Element gemeinsam haben, alle Gruppen in den beiden Mengen isomorph sind. Sie können zu einem einzigen Satz zusammengefasst werden. Da L [X] in den durch L [X + ...] generierten Kombinationen niemals vorkommt, weist jede Menge von Isomorphismen nach der Aggregation ein eindeutiges Element auf. Um die Anzahl der Isomorphismen zu ermitteln, ist es ausreichend zu zählen, wie viele Gruppen in allen Gruppen isomorpher Gruppen genau einmal vorkommen. Dazu packe ich die Sets aus, sodass sie wie folgt aussehen: [L [0], Y1, Y2, ..., L [1], Y1, ...] , sortiere die Liste, um Cluster derselben Gruppe zu erstellen, und schließlich RLE-kodiere es.
Das war's Leute.
quelle
CJam, 73 Bytes
Die zeitliche Komplexität des obigen Codes ist schlimmer als O (n! N ) .
Eingabe n = 4 ist dem Online-Dolmetscher schon zu viel .
Verwendung des Java-Interpreters ist die Eingabe von n = 5 möglich, wenn Sie über genügend RAM und Geduld verfügen.
Gruppen finden
Bei einer gegebenen Gruppe (G, ∗) der Ordnung n können wir eine beliebige Bijektion φ auswählen : G -> C n, so dass φ (e) = 0 ist .
φ wird zu einem Isomorphismus von (G, ∗) und (C n , ∗ '), wenn wir ∗' durch x ∗ 'y = φ definieren (φ -1 (x) φ -1 (y)) .
Dies bedeutet, dass es ausreicht, alle Gruppenoperatoren in C n so zu untersuchen, dass 0 das neutrale Element ist.
Wir werden einen Gruppenoperator ∗ in C n durch ein rechteckiges Array T mit den Dimensionen n × n darstellen, so dass T [x] [y] = x ∗ y ist .
Um ein solches Array zu erzeugen, können wir zunächst eine Permutation von C n für jede seiner n Zeilen auswählen.
Auf diese Weise ist 0 in allen Zeilen (aber nicht unbedingt in allen Spalten ) vorhanden, was bedeutet, dass die dritte Bedingung (Existenz einer Inversen) erfüllt ist, unabhängig davon, was e sein mag.
Wir können e = 0 festlegen, indem wir voraussetzen , dass die erste Spalte von T gleich C n ist . Insbesondere gilt die zweite Bedingung (Vorhandensein eines neutralen Elements).
Um zu überprüfen, ob T einem Gruppenoperator entspricht, müssen Sie lediglich überprüfen, ob die erste Bedingung (Assoziativität) erfüllt ist. Dies kann erschöpfend erfolgen, indem überprüft wird, dass T [T [x] [y] [z] == T [x] [T [y] [z]] für alle x, y, z in C n ist .
Zählen von nicht isomorphen Gruppen
Das obige Verfahren zum Auffinden von Gruppen ergibt einige isomorphe Gruppen. Anstatt zu identifizieren, welche isomorph sind, erzeugen wir die Familie aller isomorphen Gruppen für jede von ihnen.
Dies kann erreicht werden, indem über alle Bijektionen φ: C n -> C n iteriert wird und das zugehörige Array Tφ bestimmt wird , das durch Tφ [x] [y] = φ –1 definiert ist (T [φ (x)] [φ (y )]) .
Alles, was zu tun bleibt, ist die Anzahl der verschiedenen Familien zu zählen.
Was der Code macht
quelle
Python 2 ,
515507 BytesProbieren Sie es online!
Link zur ausführlichen Version .
quelle
s
undG
Materie? Wenn nicht, können Siedef f(k,*s):...f(~-k,j,*s)...
und verwendendef c(k,*G):...c(~-k,s,*G)....
.