Ist die Gruppe zyklisch?

21

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, ein dem a $ e = a = e $ afür alle ain der Gruppe ( Identität ). Für jedes Element ain der Gruppe gibt es genau ein Element b, das a $ b = e = b $ a( invers ) Für jeweils zwei Elemente a, bin der Gruppe a $ bbefindet sich in der Gruppe ( Abschluss ).

Wir können a^nanstelle von schreiben a$a$a$...$a.

Das zyklische Untergruppe von jedem Element erzeugt ain der Gruppe ist , <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}wo ndie 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 $ 3nicht 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.

HyperNeutrino
quelle
Ist eine 0-indizierte Eingabe zulässig? (zB [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]])?
Neil
@Neil Ja; Ich habe vergessen anzugeben. Vielen Dank!
HyperNeutrino
5
Sie sollten die Beschriftungen Ihrer Gruppenelemente in den Testfällen stärker voraussetzen. Im Moment ist die erste Zeile und Spalte der Tabelle immer [1..n]diejenige, die Fehler in einigen Antworten verbergen kann.
Lynn
3
Es sieht so aus, als würde geprüft, ob die Gruppe abelisch ist, um die Testfälle zu bestehen. Testfälle wie Z_2 * Z_2 würden dies beheben.
25.
2
@HyperNeutrino: Das ist das direkte Produkt der Zwei-Elemente-Gruppe mit sich selbst - auch bekannt als die Klein-Vier-Gruppe .
Henning Makholm

Antworten:

8

J , 8 Bytes

1:e.#@C.

Probieren Sie es online!

Erläuterung

1:e.#@C.  Input: matrix M
      C.  Convert each row from a permutation to a list of cycles
    #@    Number of cycles in each row
1:        Constant function 1
  e.      Is 1 a member of the cycle lengths?
Meilen
quelle
Dies könnte auch sein 1 e.#@C., fwiw
Conor O'Brien
Huh, J schlägt Jelly‽
Adám
@ Adám Jelly verfügt nicht über eine integrierte Funktion zum Konvertieren von Permutationen zwischen Direkt- und Zyklusnotation. Ich könnte sie wahrscheinlich später als Atome hinzufügen, was ŒCL€1ein Jelly 6 Bytes ergibt.
Meilen
8

Schale , 11 10 9 Bytes

VS≡`ȯU¡!1

1-basiert. Gibt den Index eines Generators zurück, falls vorhanden, andernfalls 0. Probieren Sie es online!

Erläuterung

V          Does any row r of the input satisfy this:
      ¡!    If you iterate indexing into r
   `    1   starting with 1
    ȯU      until a repetition is encountered,
 S≡         the result has the same length as r.
Zgarb
quelle
3

JavaScript (ES6), 52 Byte

a=>a.some(b=>!a[new Set(a.map(_=>r=b[r],r=0)).size])
Neil
quelle
3

Python 2 , 96 91 97 Bytes

lambda x:any(g(r,r[i],i+1)==len(r)for i,r in enumerate(x))
g=lambda x,y,z:y==z or 1+g(x,x[y-1],z)

Probieren Sie es online!

Halvard Hummel
quelle
or 1+g-> or-~g.
Jonathan Frech
2

Gelee , 15 Bytes

JŒ!ị@€µṂ⁼Jṙ'’$$

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!) ...)

JŒ!ị@€             Generate all ways to denote this group.
                     (by indexing into every permutation of 1…n)
      µṂ⁼          Is the smallest one equal to this?
         Jṙ'’$$      [[1 2 …  n ]
                      [2 3 …  1 ]    (the group table for Z_n)
                      [… … …  … ]
                      [n 1 … n-1]]
Lynn
quelle
Huh das ist ein interessanter Ansatz; Daran hätte ich nie gedacht! +1
HyperNeutrino
2

R , 101 97 Bytes

function(m)any(sapply(1:(n=nrow(m)),function(x)all(1:n%in%Reduce(`[`,rep(list(m[x,]),n),x,T,T))))

Überprüfen Sie alle Testfälle

Dies berechnet einfach <g>für jedes g \in Gund testet dann G \subseteq <g>, ob und ob eines davon wahr ist. Da wir jedoch immer $gauf der rechten Seite anwenden , replizieren wir m[g,](die gdritte Zeile) und indizieren dann mit dem Ergebnis der Anwendung in diese Zeile. Dabei werden die Ergebnisse $gakkumuliert und nicht m[g,g$g]jedes Mal verwendet, wodurch etwa 4 Byte eingespart werden.

Giuseppe
quelle
1

Clojure, 68 Bytes

#(seq(for[l % :when(apply distinct?(take(count l)(iterate l 0)))]l))
NikoNyrh
quelle
1

Python 2 , 82 Bytes

lambda A:len(A)in[len(set(reduce(lambda a,c:a+[A[a[-1]][n]],A,[n])))for n in A[0]]

Probieren Sie es online!

0-indizierte Cayley-Tabelle wird eingegeben; True / False-Ausgabe für zyklische / nicht zyklische Gruppe.

Chas Brown
quelle