Introducción

Puede omitir esta parte si ya sabe qué es un grupo cíclico.

Un grupo se define por un conjunto y una operación binaria asociativa $(es decir, (a $ b) $ c = a $ (b $ c)existe exactamente un elemento en el grupo edonde a $ e = a = e $ apara todos aen el grupo ( identidad ). Para cada elemento aen el grupo existe exactamente uno btal que a $ b = e = b $ a( inverso ) Por cada dos elementos a, ben el grupo, a $ bestá en el grupo ( cierre ).

Podemos escribir a^nen lugar de a$a$a$...$a.

El subgrupo cíclico generado por cualquier elemento aen el grupo es <a> = {e, a, a^2, a^3, a^4, ..., a^(n-1)}donde nestá el orden (tamaño) del subgrupo (a menos que el subgrupo sea infinito).

Un grupo es cíclico si puede ser generado por uno de sus elementos.

Reto

Dada la tabla de Cayley (tabla de productos) para un grupo finito, determine si es o no cíclico.

Ejemplo

Echemos un vistazo a la siguiente tabla de Cayley:

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

(Esta es la tabla de Cayley para el Grupo Diédrico 3, D_3).

Esto está indexado en 1, así que si queremos encontrar el valor de 5 $ 3, miramos en la quinta columna en la tercera fila (tenga en cuenta que el operador no es necesariamente conmutativo, por 5 $ 3lo que no es necesariamente igual a 3 $ 5. Vemos aquí eso 5 $ 3 = 6(también que 3 $ 5 = 4)

Podemos encontrar <3>comenzando con [3], y luego, mientras la lista es única, agregue el producto del último elemento y el generador (3). Nosotros conseguimos [3, 3 $ 3 = 2, 2 $ 3 = 1, 1 $ 3 = 3]. Nos detenemos aquí con el subgrupo {3, 2, 1}.

Si calcula <1>a través <6>verá que ninguno de los elementos del grupo de generar todo el grupo. Por lo tanto, este grupo no es cíclico.

Casos de prueba

La entrada se dará como una matriz, la salida como un valor de decisión verdadero / falso.

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

Se le garantizará que la entrada sea siempre un grupo.

Puede tomar la entrada como valores indexados a 0.

J , 8 bytes

1:e.#@C.

Pruébalo en línea!

Explicación

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?

Casco , 11 10 9 bytes

VS≡`ȯU¡!1

Basado en 1. Devuelve el índice de un generador si existe uno, 0 de lo contrario. Pruébalo en línea!

Explicación

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.

Jalea , 13 11 bytes

ị"⁸$ÐĿ«/E€Ẹ

Pruébalo en línea!

JavaScript (ES6), 52 bytes

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

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)

Pruébalo en línea!

Jalea , 15 bytes

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

Pruébalo en línea!

Primera idea tonta que se me ocurrió: verificar si hay isomorfismo en Z _n . (Este código es 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 bytes

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

Verificar todos los casos de prueba

Esto simplemente calcula <g>para cada uno g \in Gy luego prueba si G \subseteq <g>, luego verifica si alguno de ellos es verdadero. Sin embargo, dado que siempre estamos aplicando$g a la derecha, replicamos m[g,](la gfila th) y luego indexamos en esa fila con el resultado de la aplicación $g, acumulando los resultados en lugar de usar m[g,g$g]cada vez, lo que ahorró alrededor de 4 bytes.

Clojure, 68 bytes

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

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]]

Pruébalo en línea!

Se ingresa la tabla Cayley indexada en 0; Salida verdadero / falso para el grupo cíclico / no cíclico.