Définitions

Vous pouvez ignorer cette partie si vous connaissez déjà les définitions des groupes , des groupes finis et des sous - groupes .

Groupes

En algèbre abstraite, un groupe est un tuple (G, ∗) , où G est un ensemble et ∗ est une fonction G × G → G telle que:

• Fermeture: pour tout x, y dans G , x ∗ y est aussi dans G (sous-entendu par le fait que ∗ est une fonction G × G → G ).

• Associativité: pour tout x, y, z dans G , (x ∗ y) ∗ z = x ∗ (y ∗ z) .

• Identité: il existe un élément e dans G tel que pour tout x dans G , x ∗ e = x = e ∗ x .

• Inverse: pour chaque x dans G , il existe un élément y dans G tel que x ∗ y = e = y ∗ x , où e est l'élément d'identité mentionné au point précédent.

Groupes finis

Un groupe fini est un groupe (G, ∗) où G est fini, c'est-à-dire qu'il a un nombre fini d'éléments.

Sous-groupes

Un sous-groupe (H, ∗) d'un groupe (G, ∗) est tel que H est un sous-ensemble de G (pas nécessairement un sous-ensemble approprié) et (H, ∗) est également un groupe (c'est-à-dire qu'il satisfait aux 4 critères ci-dessus).

Exemples

Considérons le groupe dièdre D ₃ (G, ∗) où G = {1, A, B, C, D, E} et ∗ est défini ci-dessous (un tableau comme celui-ci est appelé un tableau de Cayley ):

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

Dans ce groupe, l'identité est 1 . De plus, A et B sont des inverses l'un de l'autre, tandis que 1 , C , D et E sont respectivement les inverses d'eux-mêmes (l'inverse de 1 est 1 , l'inverse de C est C , l'inverse de D est D et le l'inverse de E est E ).

Maintenant, nous pouvons vérifier que (H, ∗) où H = {1, A, B} est un sous-groupe de (G, ∗) . Pour la fermeture, reportez-vous au tableau ci-dessous:

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

où toutes les paires possibles d'éléments en H de moins * donnent un membre en H .

Le associativité ne nécessite pas de contrôle, puisque les éléments de H sont des éléments de G .

L'identité est 1 . Cela doit être le même avec l'identité du groupe. De plus, l'identité dans un groupe doit être unique. (Pouvez-vous le prouver?)

Pour l'inverse, vérifier que l'inverse de A est B , qui est un membre d' H . L'inverse de B est A , qui est également un membre de H . L'inverse de 1 est toujours lui-même, ce qui ne nécessite pas de vérification.

Tâche

La description

Étant donné un groupe fini (G, ∗) , trouvez le nombre de ses sous-groupes.

Contribution

Pour un groupe (G, *) , vous recevrez un tableau 2D de taille n × n , où n est le nombre d'éléments dans G . Supposons que l'index 0est l'élément d'identité. Le tableau 2D représentera la table de multiplication. Par exemple, pour le groupe ci-dessus, vous recevrez le tableau 2D suivant:

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

Par exemple, vous pouvez voir que 3 ∗ 1 = 5 car a[3][1] = 5, où aest le tableau 2D ci-dessus.

Remarques:

• Vous pouvez utiliser un tableau 2D indexé 1.
• La ligne et la colonne de l'identité peuvent être omises.
• Vous pouvez utiliser d'autres formats comme bon vous semble, mais il doit être cohérent. (c'est-à-dire que vous souhaiterez peut-être plutôt que le dernier index soit l'identité, etc.)

Production

Un nombre positif représentant le nombre de sous-groupes dans le groupe.

Par exemple, pour le groupe ci-dessus, (H, ∗) est un sous-groupe de (G, ∗) chaque fois que H =

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

Par conséquent, il existe 6 sous-groupes et votre sortie pour cet exemple devrait être 6.

Conseils

Vous pouvez lire les articles auxquels j'ai lié. Ces articles contiennent des théorèmes sur les groupes et les sous-groupes qui pourraient vous être utiles.

Notation

C'est du code-golf . Réponse avec le plus petit nombre de victoires d'octets.

Mathematica, 62 48 octets

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

Fonction pure qui attend un tableau 2D indexé 1. Counts le numéro de Subsetsla Firstligne du tableau d'entrée qui est fermée sous l'opération de groupe. Puisque cela inclura l'ensemble vide, nous soustrayons 1. Notez qu'un sous-ensemble non vide d'un groupe fini qui est fermé sous l'opération de groupe est en fait un sous-groupe (et vice versa, par définition).

À strictement parler, je ne vérifie pas que le sous x- ensemble est fermé sous l'opération de groupe, je limite la table de multiplication au sous-ensemble xet vérifie qu'elle contient précisément les éléments de x. De toute évidence, cela implique qu'il xest fermé par rapport à l'opération de groupe. Inversement, tout sous x- groupe contiendra 1et xsera donc un sous-ensemble des éléments apparaissant dans la table de multiplication restreinte, et puisqu'il xest fermé sous l'opération de groupe, il doit être égal x.

Haskell , 79 octets

Fondamentalement, un portage de la méthode Mathematica de ngenisis. (Sauf que j'utilise des tableaux indexés 0).

cprend une liste de listes de Ints et retourne un entier.

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

Essayez-le en ligne!

On suppose que les Ints sont numérotés de la même manière que les lignes (listes externes) et les colonnes montrant leur multiplication. Ainsi, puisque 0 est l'identité, la première colonne est la même que les indices des lignes. Cela permet d'utiliser les entrées de la première colonne pour construire les sous-ensembles.

Comment ça fonctionne

• c est la fonction principale.
• g est le tableau de groupe sous forme de liste de listes.
• lest un sous-ensemble des éléments. La liste des sous-ensembles est construite comme suit:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]greplie une fonction sur les rangées de g.
  • rest une ligne de g, dont le premier (0ème) élément est extrait en tant qu'élément qui peut être inclus ( (r!!0:)) ou non ( id).
  • <*> combine les choix pour cette ligne avec les suivants.
• and[g!!x!!y`elem`l|x<-l,y<-l]teste pour chaque paire d'éléments lsi leur multiple est dedans l.
• sum[1|...]-1 compte les sous-ensembles qui réussissent le test, sauf un, le sous-ensemble vide.

Gelée , 17 16 octets

1 octet grâce à 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.

Essayez-le en ligne! (1 index)

Python 2, 297 215 octets

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

Essayez-le en ligne

Ce programme fonctionne pour le groupe d'exemple sans ==T[x][y], mais je suis toujours sûr qu'il est nécessaire.

Edit: suppose maintenant que l'élément d'identité de G est toujours le premier.

Non 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 non golfé

Les éléments de groupe négatifs peuvent être pris en charge gratuitement en passant -1à ''.