Einführung
Sie können diesen Teil überspringen, wenn Sie bereits wissen, was eine zyklische Gruppe ist.
Eine Gruppe wird durch eine Menge und eine assoziative Binäroperation definiert $
(d (a $ b) $ c = a $ (b $ c)
. H. Es gibt genau ein Element in der Gruppe, e
in dem a $ e = a = e $ a
für alle a
in der Gruppe ( Identität ). Für jedes Element a
in der Gruppe gibt es genau ein Element b
, das a $ b = e = b $ a
( invers ) Für jeweils zwei Elemente a, b
in der Gruppe a $ b
befindet sich in der Gruppe ( Abschluss ).
Wir können a^n
anstelle von schreiben a$a$a$...$a
.
Das zyklische Untergruppe von jedem Element erzeugt a
in der Gruppe ist , <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}
wo n
die Ordnung (Größe) der Untergruppe (es sei denn , die Untergruppe ist unendlich).
Eine Gruppe ist zyklisch, wenn sie von einem ihrer Elemente erzeugt werden kann.
Herausforderung
Bestimmen Sie anhand der Cayley-Tabelle (Produkttabelle) für eine endliche Gruppe, ob sie zyklisch ist oder nicht.
Beispiel
Werfen wir einen Blick auf die folgende Cayley-Tabelle:
1 2 3 4 5 6
2 3 1 6 4 5
3 1 2 5 6 4
4 5 6 1 2 3
5 6 4 3 1 2
6 4 5 2 3 1
(Dies ist die Cayley-Tabelle für Diedergruppe 3, D_3).
Dies ist 1-indiziert. Wenn wir also den Wert von ermitteln möchten 5 $ 3
, sehen wir in der fünften Spalte in der dritten Zeile nach (beachten Sie, dass der Operator nicht unbedingt kommutativ ist, also 5 $ 3
nicht unbedingt gleich 3 $ 5
. Wir sehen hier, dass 5 $ 3 = 6
(auch das 3 $ 5 = 4
).
Wir können finden, <3>
indem wir mit beginnen [3]
und dann, während die Liste eindeutig ist, das Produkt des letzten Elements und den Generator (3) anhängen. Wir bekommen [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]
. Wir hören hier mit der Untergruppe auf {3, 2, 1}
.
Wenn Sie durchrechnen, <1>
werden <6>
Sie feststellen, dass keines der Elemente in der Gruppe die gesamte Gruppe generiert. Somit ist diese Gruppe nicht zyklisch.
Testfälle
Die Eingabe wird als Matrix angegeben, die Ausgabe als wahrheitsgetreuer / falscher Entscheidungswert.
[[1,2,3,4,5,6],[2,3,1,6,4,5],[3,1,2,5,6,4],[4,5,6,1,2,3],[5,6,4,3,1,2],[6,4,5,2,3,1]] -> False (D_3)
[[1]] -> True ({e})
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3]] -> True ({1, i, -1, -i})
[[3,2,4,1],[2,4,1,3],[4,1,3,2],[1,3,2,4]] -> True ({-1, i, -i, 1})
[[1,2],[2,1]] -> True ({e, a} with a^-1=a)
[[1,2,3,4,5,6,7,8],[2,3,4,1,6,7,8,5],[3,4,1,2,7,8,5,6],[4,1,2,3,8,5,6,7],[5,8,7,6,1,4,3,2],[6,5,8,7,2,1,4,3],[7,6,5,8,3,2,1,4],[8,7,6,5,4,3,2,1]] -> False (D_4)
[[1,2,3,4,5,6],[2,1,4,3,6,5],[3,4,5,6,1,2],[4,3,6,5,2,1],[5,6,1,2,3,4],[6,5,2,1,4,3]] -> True (product of cyclic subgroups of order 2 and 3, thanks to Zgarb)
[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,1,2]] -> False (Abelian but not cyclic; thanks to xnor)
Sie werden garantiert, dass die Eingabe immer eine Gruppe ist.
Sie können Eingaben als 0-indizierte Werte annehmen.
quelle
[[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
)?[1..n]
diejenige, die Fehler in einigen Antworten verbergen kann.Antworten:
J , 8 Bytes
Probieren Sie es online!
Erläuterung
quelle
1 e.#@C.
, fwiwŒCL€1e
in Jelly 6 Bytes ergibt.Schale ,
11 109 Bytes1-basiert. Gibt den Index eines Generators zurück, falls vorhanden, andernfalls 0. Probieren Sie es online!
Erläuterung
quelle
Jelly ,
1311 BytesProbieren Sie es online!
quelle
JavaScript (ES6), 52 Byte
quelle
Python 2 ,
969197 BytesProbieren Sie es online!
quelle
or 1+g
->or-~g
.Gelee , 15 Bytes
Probieren Sie es online!
Erste dumme Idee, die mir in den Sinn kam: Überprüfen Sie, ob Z n isomorph ist . (Dieser Code ist O (n!) ...)
quelle
R ,
10197 BytesÜberprüfen Sie alle Testfälle
Dies berechnet einfach
<g>
für jedesg \in G
und testet dannG \subseteq <g>
, ob und ob eines davon wahr ist. Da wir jedoch immer$g
auf der rechten Seite anwenden , replizieren wirm[g,]
(dieg
dritte Zeile) und indizieren dann mit dem Ergebnis der Anwendung in diese Zeile. Dabei werden die Ergebnisse$g
akkumuliert und nichtm[g,g$g]
jedes Mal verwendet, wodurch etwa 4 Byte eingespart werden.quelle
Clojure, 68 Bytes
quelle
Python 2 , 82 Bytes
Probieren Sie es online!
0-indizierte Cayley-Tabelle wird eingegeben; True / False-Ausgabe für zyklische / nicht zyklische Gruppe.
quelle