introduction

Vous pouvez ignorer cette partie si vous savez déjà ce qu'est un groupe cyclique.

Un groupe est défini par un ensemble et une opération binaire associative $(c'est-à-dire (a $ b) $ c = a $ (b $ c). Il existe exactement un élément dans le groupe eoù a $ e = a = e $ apour tous adans le groupe ( identité ). Pour chaque élément adu groupe, il en existe exactement un btel que a $ b = e = b $ a( inverse ) Pour tous les deux éléments a, bdu groupe, a $ best dans le groupe ( fermeture ).

Nous pouvons écrire a^nà la place de a$a$a$...$a.

Le sous-groupe cyclique généré par n'importe quel élément adu groupe est <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}où nest l'ordre (taille) du sous-groupe (sauf si le sous-groupe est infini).

Un groupe est cyclique s'il peut être généré par l'un de ses éléments.

Défi

Étant donné la table Cayley (tableau des produits) pour un groupe fini, déterminez si elle est cyclique ou non.

Exemple

Jetons un coup d'œil au tableau Cayley suivant:

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

(Il s'agit du tableau de Cayley pour le groupe dièdre 3, D_3).

Ceci est indexé sur 1, donc si nous voulons trouver la valeur de 5 $ 3, nous regardons dans la cinquième colonne de la troisième ligne (notez que l'opérateur n'est pas nécessairement commutatif, donc 5 $ 3n'est pas nécessairement égal à 3 $ 5. Nous voyons ici que 5 $ 3 = 6(aussi que 3 $ 5 = 4).

On peut trouver <3>en commençant par [3], puis alors que la liste est unique, ajouter le produit du dernier élément et le générateur (3). Nous obtenons [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]. Nous nous arrêtons ici avec le sous-groupe {3, 2, 1}.

Si vous calculez à <1>travers <6>vous verrez qu'aucun des éléments du groupe génèrent tout le groupe. Ainsi, ce groupe n'est pas cyclique.

Cas de test

L'entrée sera donnée sous forme de matrice, la sortie sous forme de valeur de décision véridique / fausse.

[[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)

Vous serez assuré que l'entrée est toujours un groupe.

Vous pouvez prendre l'entrée comme des valeurs indexées 0.

J , 8 octets

1:e.#@C.

Essayez-le en ligne!

Explication

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?

Husk , 11 10 9 octets

VS≡`ȯU¡!1

1 basé. Renvoie l'index d'un générateur s'il existe, 0 sinon. Essayez-le en ligne!

Explication

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.

Gelée , 13 11 octets

ị"⁸$ÐĿ«/E€Ẹ

Essayez-le en ligne!

JavaScript (ES6), 52 octets

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

Python 2 , 96 91 97 octets

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)

Essayez-le en ligne!

Gelée , 15 octets

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

Essayez-le en ligne!

Première idée idiote qui m'est venue à l'esprit: vérifier l'isomorphisme de Z _n . (Ce code est 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]]

R , 101 97 octets

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

Vérifier tous les cas de test

Cela calcule simplement <g>pour chacun g \in G, puis teste si G \subseteq <g>, puis vérifie si certains d'entre eux sont vrais. Cependant, puisque nous appliquons toujours $gà droite, nous répliquons m[g,](la gtroisième ligne) puis indexons dans cette ligne avec le résultat de l'application $g, en accumulant les résultats plutôt qu'en les utilisant à m[g,g$g]chaque fois, ce qui a permis d'économiser environ 4 octets.

Clojure, 68 octets

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

Python 2 , 82 octets

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

Essayez-le en ligne!

La table Cayley indexée 0 est entrée; Sortie vrai / faux pour le groupe cyclique / non cyclique.