Definitionen

Sie können diesen Teil überspringen, wenn Sie bereits die Definitionen von Gruppen , endlichen Gruppen und Untergruppen kennen .

Gruppen

In der abstrakten Algebra ist eine Gruppe ein Tupel (G, ∗) , wobei G eine Menge und ∗ eine Funktion G × G → G ist, so dass gilt:

• Abschluss: für alle x, y in G ist x ∗ y auch in G (impliziert durch die Tatsache, dass ∗ eine Funktion G × G → G ist ).

• Assoziativität: für alle x, y, z in G ist (x ∗ y) ∗ z = x ∗ (y ∗ z) .

• Identität: gibt es ein Element e in G so dass für alle x in G , x * e = x = e * x .

• Invers: Für jedes x in G gibt es ein Element y in G, so dass x x y = e = y ∗ x ist , wobei e das Identitätselement ist, das im vorherigen Aufzählungspunkt erwähnt wurde.

Endliche Gruppen

Eine endliche Gruppe ist eine Gruppe (G, ∗), in der G endlich ist, dh endlich viele Elemente hat.

Untergruppen

Eine Untergruppe (H, ∗) einer Gruppe (G, ∗) ist so, dass H eine Untergruppe von G ist (nicht notwendigerweise eine richtige Untergruppe) und (H, ∗) ebenfalls eine Gruppe ist (dh die obigen 4 Kriterien erfüllt).

Beispiele

Betrachten Sie die Diedergruppe D ₃ (G, ∗), wobei G = {1, A, B, C, D, E} und ∗ wie folgt definiert sind (eine Tabelle wie diese wird als Cayley-Tabelle bezeichnet ):

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

In dieser Gruppe ist die Identität 1 . Auch A und B sind invers zueinander sind, während 1 , C , D und E die Inversen der sich jeweils (der Kehrwert sind 1 ist 1 , das Inverse von C ist , C , das Inverse von D ist D , und die Inverse von E ist E ).

Nun können wir überprüfen, dass (H, ∗) wobei H = {1, A, B} eine Untergruppe von (G, ∗) ist . Informationen zum Verschluss finden Sie in der folgenden Tabelle:

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

wo alle möglichen Elementpaare in H unter ∗ ein Glied in H ergeben .

Die Assoziativität muss nicht überprüft werden, da Elemente von H Elemente von G sind .

Die Identität ist 1 . Dies muss mit der Gruppenidentität identisch sein. Außerdem muss die Identität in einer Gruppe eindeutig sein. (Können Sie das beweisen?)

Für die inversen prüfen , dass die Inverse von A ist , B , das ein Mitglied ist H . Die Umkehrung von B ist A , das auch ein Mitglied von H ist . Das Inverse von 1 ist immer noch selbst, was keine Überprüfung erfordert.

Aufgabe

Beschreibung

Bestimmen Sie bei einer endlichen Gruppe (G, ∗) die Anzahl ihrer Untergruppen.

Eingang

Für eine Gruppe (G, ∗) erhalten Sie ein 2D-Array der Größe n × n , wobei n die Anzahl der Elemente in G ist . Angenommen, der Index 0ist das Identitätselement. Das 2D-Array repräsentiert die Multiplikationstabelle. Für die obige Gruppe erhalten Sie beispielsweise das folgende 2D-Array:

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

Zum Beispiel können Sie sehen, dass 3 ∗ 1 = 5 ist, weil a[3][1] = 5, wo adas 2D-Array oben ist.

Anmerkungen:

• Sie können ein 1-indiziertes 2D-Array verwenden.
• Die Zeile und die Spalte für die Identität können weggelassen werden.
• Sie können nach Belieben andere Formate verwenden, diese müssen jedoch konsistent sein. (dh Sie möchten möglicherweise, dass der letzte Index stattdessen Identität ist usw.)

Ausgabe

Eine positive Zahl, die die Anzahl der Untergruppen in der Gruppe darstellt.

Beispielsweise ist für die obige Gruppe (H, above ) eine Untergruppe von (G, ∗), wann immer H =

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

Daher gibt es 6 Untergruppen, und Ihre Ausgabe für dieses Beispiel sollte sein 6.

Hinweise

Sie können die Artikel lesen, die ich verlinkt habe. Diese Artikel enthalten Theoreme über Gruppen und Untergruppen, die für Sie nützlich sein könnten.

Wertung

Das ist Code-Golf . Antwort mit der niedrigsten Anzahl an Bytes gewinnt.

Mathematica, 62 48 Bytes

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

Reine Funktion, die ein 1-indiziertes 2D-Array erwartet. Counts die Nummer Subsetsder FirstZeile des Eingabearrays, die unter der Gruppenoperation geschlossen wird. Da dies die leere Menge einschließt, subtrahieren wir 1. Beachten Sie, dass eine nicht leere Untergruppe einer endlichen Gruppe, die unter der Gruppenoperation geschlossen wird , per Definition eine Untergruppe ist (und umgekehrt).

Streng genommen überprüfe ich nicht, ob die Teilmenge xunter der Gruppenoperation geschlossen ist x, sondern beschränke die Multiplikationstabelle auf die Teilmenge und überprüfe, ob sie genau die Elemente von enthält x. Dies impliziert eindeutig, dass xin Bezug auf die Gruppenoperation geschlossen ist. Im Gegensatz dazu jede Untergruppe xenthält 1und somit xeine Teilmenge der Elemente in der eingeschränkten Multiplikationstabelle erscheinen wird, und da xunter dem Gruppenbetrieb geschlossen ist, muss es gleich x.

Haskell , 79 Bytes

Grundsätzlich eine Portierung der Mathematica-Methode von ngenisis. (Außer ich verwende 0-indizierte Arrays.)

cNimmt eine Liste von Listen von Ints und gibt eine ganze Zahl zurück.

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

Probieren Sie es online!

Es wird angenommen, dass die Ints genauso nummeriert sind wie die Zeilen (äußeren Listen) und Spalten, die ihre Multiplikation anzeigen. Da also 0 die Identität ist, entspricht die erste Spalte den Indizes der Zeilen. Dies ermöglicht die Verwendung der Einträge der ersten Spalte zum Aufbau der Teilmengen.

Wie es funktioniert

• c ist die Hauptfunktion.
• g ist das Gruppenarray als Liste von Listen.
• list eine Teilmenge der Elemente. Die Liste der Teilmengen ist wie folgt aufgebaut:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]gfaltet eine Funktion über die Zeilen von g.
  • rist eine Zeile von g, deren erstes (0.) Element als Element extrahiert wird, das eingeschlossen sein kann ( (r!!0:)) oder nicht ( id).
  • <*> kombiniert die Auswahlmöglichkeiten für diese Zeile mit den folgenden.
• and[g!!x!!y`elem`l|x<-l,y<-l]testet für jedes Elementpaar, lob sein Vielfaches vorhanden ist l.
• sum[1|...]-1 zählt die Teilmengen, die den Test bestehen, mit Ausnahme einer leeren Teilmenge.

Jelly , 17 16 Bytes

1 Byte dank 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.

Probieren Sie es online! (1-indiziert)

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

Probieren Sie es online aus

Dieses Programm funktioniert für die Beispielgruppe ohne ==T[x][y], aber ich bin mir ziemlich sicher, dass es notwendig ist.

Bearbeiten: Nimmt nun an, dass das Identitätselement von G immer das erste ist.

Ungolfed:

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

Ungolfed TIO

Negative Gruppenelemente durch Veränderung ohne Kosten unterstützt werden -1zu ''.