Definiciones

Puede omitir esta parte si ya conoce las definiciones de grupos , grupos finitos y subgrupos .

Grupos

En álgebra abstracta, un grupo es una tupla (G, ∗) , donde G es un conjunto y ∗ es una función G × G → G tal que se cumple lo siguiente:

• Cierre: para todo x, y en G , x ∗ y también está en G (implicado por el hecho de que ∗ es una función G × G → G ).

• Asociatividad: para todos los x, y, z en G , (x ∗ y) ∗ z = x ∗ (y ∗ z) .

• Identidad: existe un elemento e en G tal que para todo x en G , x ∗ e = x = e ∗ x .

• Inverso: para cada x en G , existe un elemento y en G tal que x ∗ y = e = y ∗ x , donde e es el elemento de identidad mencionado en el punto anterior.

Grupos finitos

Un grupo finito es un grupo (G, ∗) donde G es finito, es decir, tiene muchos elementos.

Subgrupos

Un subgrupo (H, ∗) de un grupo (G, ∗) es tal que H es un subconjunto de G (no necesariamente un subconjunto apropiado) y (H, ∗) también es un grupo (es decir, satisface los 4 criterios anteriores).

Ejemplos

Considere el grupo diédrico D ₃ (G, ∗) donde G = {1, A, B, C, D, E} y ∗ se definen a continuación (una tabla como esta se llama tabla de Cayley ):

∗ | 1 ABCDE
- + ----------------------
1 | 1 ABCDE
A | AB 1 DIC
B | B 1 AECD
C | CED 1 BA
D | DCEA 1 B
E | EDCBA 1

En este grupo, la identidad es 1 . Además, A y B son inversos entre sí, mientras que 1 , C , D y E son inversos de sí mismos respectivamente (el inverso de 1 es 1 , el inverso de C es C , el inverso de D es D y el inverso de E es E ).

Ahora, podemos verificar que (H, ∗) donde H = {1, A, B} es un subgrupo de (G, ∗) . Para el cierre, consulte la tabla a continuación:

∗ | 1 AB
- + ----------
1 | 1 AB
A | AB 1
B | B 1 A

donde todos los posibles pares de elementos en H bajo * dan un miembro en H .

La asociatividad no requiere la comprobación, ya que los elementos de H son elementos de G .

La identidad es 1 . Esto debe ser lo mismo con la identidad del grupo. Además, la identidad en un grupo debe ser única. (¿Puedes probar esto?)

Para la inversa, compruebe que la inversa de A es B , que es un miembro de H . La inversa de B es A , que es también un miembro de H . El inverso de 1 sigue siendo el mismo, que no requiere verificación.

Tarea

Descripción

Dado un grupo finito (G, ∗) , encuentre el número de sus subgrupos.

Entrada

Para un grupo (G, *) , recibirá una matriz 2D de tamaño n × n , donde n es el número de elementos en G . Suponga que el índice 0es el elemento de identidad. La matriz 2D representará la tabla de multiplicar. Por ejemplo, para el grupo anterior, recibirá la siguiente matriz 2D:

[[0, 1, 2, 3, 4, 5],
[1, 2, 0, 4, 5, 3],
[2, 0, 1, 5, 3, 4],
[3, 5, 4, 0, 2, 1],
[4, 3, 5, 1, 0, 2],
[5, 4, 3, 2, 1, 0]]

Por ejemplo, puede ver que 3 ∗ 1 = 5 porque a[3][1] = 5, donde aestá la matriz 2D arriba.

Notas:

• Puede usar una matriz 2D indexada 1.
• La fila y la columna para la identidad se pueden omitir.
• Puede usar otros formatos como mejor le parezca, pero debe ser coherente. (es decir, es posible que desee que el último índice sea identidad, etc.)

Salida

Un número positivo que representa el número de subgrupos en el grupo.

Por ejemplo, para el grupo anterior, (H, ∗) es un subgrupo de (G, ∗) siempre que H =

• {1}
• {1, A, B}
• {1, C}
• {1, D}
• {1, E}
• {1, A, B, C, D, E}

Por lo tanto, hay 6 subgrupos, y su salida para este ejemplo debería ser 6.

Consejos

Puedes leer los artículos que he vinculado. Esos artículos contienen teoremas sobre grupos y subgrupos que pueden serle útiles.

Puntuación

Este es el código de golf . Responda con el menor recuento de bytes gana.

Mathematica, 62 48 bytes

Count[Subsets@First@#,x_/;Union@@#[[x,x]]==x]-1&

Función pura que espera una matriz 2D indexada 1. Counts el número deSubsets la Firstfila de la matriz de entrada que están cerradas bajo la operación de grupo. Como esto incluirá el conjunto vacío, restamos 1. Tenga en cuenta que un subconjunto no vacío de un grupo finito que está cerrado bajo la operación de grupo es, de hecho, un subgrupo (y viceversa, por definición).

Estrictamente hablando, no verifico que el subconjunto xesté cerrado bajo la operación de grupo, restrinjo la tabla de multiplicación al subconjunto xy verifico que contenga precisamente los elementos de x. Claramente esto implica que xestá cerrado con respecto a la operación del grupo. Por el contrario, cualquier subgrupo xcontendrá 1y, por xlo tanto , será un subconjunto de los elementos que aparecen en la tabla de multiplicación restringida, y dado que xestá cerrado bajo la operación de grupo, debe ser igual x.

Haskell , 79 bytes

Básicamente un puerto del método Mathematica de ngenisis. (Excepto que estoy usando matrices indexadas a 0).

ctoma una lista de listas de Intsy devuelve un número entero.

c g=sum[1|l<-foldr(\r->([id,(r!!0:)]<*>))[[]]g,and[g!!x!!y`elem`l|x<-l,y<-l]]-1

Pruébalo en línea!

Se supone que los Ints están numerados de la misma manera que las filas (listas externas) y las columnas que muestran su multiplicación. Por lo tanto, dado que 0 es la identidad, la primera columna es la misma que los índices de las filas. Esto permite utilizar las entradas de la primera columna para construir los subconjuntos.

Cómo funciona

• c Es la función principal.
• g es la matriz de grupo como una lista de listas.
• lEs un subconjunto de los elementos. La lista de subconjuntos se construye de la siguiente manera:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]gpliega una función sobre las filas de g.
  • res una fila de gcuyo primer elemento (0) se extrae como un elemento que puede incluirse ( (r!!0:)) o no (id ).
  • <*> combina las opciones para esta fila con las siguientes.
• and[g!!x!!y`elem`l|x<-l,y<-l]prueba para cada par de elementos en lsi su múltiplo está en l.
• sum[1|...]-1 cuenta los subconjuntos que pasan la prueba, excepto uno, el subconjunto vacío.

Jalea , 17 16 bytes

1 byte gracias a ETHproductions ( LR → J)

ị³Z⁸ịFḟ
JŒPÇÐḟL’

JŒPÇÐḟL’  main link. one argument (2D array)
J         [1,2,3,...,length of argument]
 ŒP       power set of ^
    Ðḟ    throw away elements that pass the test...
   Ç      in the helper link
      L   length (number of elements that do not pass)
       ’  decrement (the empty set is still closed under
          multiplication, but it is not a subgroup, as
          the identity element does not exist.)

ị³Z⁸ịFḟ   helper link. one argument (1D indexing array)
ị³        elements at required indices of program input (2D array)
  Z       transpose
   ⁸ị     elements at required indices of ^
     F    flatten
      ḟ   remove elements of ^ that are in the argument given
          if the set is closed under multiplication, this will
          result in an empty set, which is considered falsey.

Pruébalo en línea! (1 indexado)

Python 2, 297 215 bytes

from itertools import*
T=input()
G=T[0]
print sum(all(T[y][x]in g for x,y in product(g,g))*all(any(T[y][x]==G[0]==T[x][y]for y in g)for x in g)*(G[0]in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

Pruébalo en línea

Este programa funciona para el grupo de ejemplo sin ==T[x][y], pero todavía estoy bastante seguro de que es necesario.

Editar: ahora se supone que el elemento de identidad de G es siempre el primero.

Sin golf:

from itertools import*
T=input()
G=T[0]
def f(x,y):return T[y][x]                                           # function
def C(g):return all(f(x,y)in g for x,y in product(g,g))             # closure
def E(g):return[all(f(x,y)==y for y in g)for x in g]                # identity

a=E(G)
e=any(a)
e=G[a.index(1)]if e else-1                                          # e in G

def I(G):return all(any(f(x,y)==e==f(y,x)for y in G)for x in G)     # inverse

#print e
#print C(G),any(E(G)),I(G)

#for g in chain(*[combinations(G,n)for n in range(len(G)+1)]):      # print all subgroups
#   if C(g)and I(g)and e in g:print g

print sum(C(g)*I(g)*(e in g)for g in chain(*[combinations(G,n)for n in range(len(G)+1)]))

TIO sin golf

Los elementos de grupo negativos se pueden admitir sin costo cambiando -1a ''.