Definicje

Możesz pominąć tę część, jeśli znasz już definicje grup , grup skończonych i podgrup .

Grupy

W algebrze abstrakcyjnej grupa jest krotką (G, ∗) , gdzie G jest zbiorem, a ∗ jest funkcją G × G → G, tak że następujące:

• Zamknięcie: dla wszystkich x, y w G , x ∗ y jest również w G (implikowane przez fakt, że ∗ jest funkcją G × G → G ).

• Asocjatywność: dla wszystkich x, y, z w G , (x ∗ y) ∗ z = x ∗ (y ∗ z) .

• Tożsamość: istnieje element e w G taki, że dla wszystkich x w G , x ∗ e = x = e ∗ x .

• Odwrotnie: dla każdego x w G istnieje element y w G, taki że x ∗ y = e = y ∗ x , gdzie e jest elementem tożsamości wspomnianym w poprzednim punkcie.

Grupy skończone

Grupa skończona to grupa (G, ∗), w której G jest skończone, tzn. Ma skończoną liczbę elementów.

Podgrupy

Podgrupa (H *) z grupy (G *) jest taka, że H jest podzbiorem G (niekoniecznie podzbiorem) i (h, *) jest grupa (tj spełnia kryteria 4 powyżej).

Przykłady

Rozważ dwuścienną grupę D ₃ (G, ∗), w której G = {1, A, B, C, D, E} i ∗ jest zdefiniowany poniżej (tabela taka jak ta nazywana jest tabelą Cayleya ):

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

W tej grupie tożsamość wynosi 1 . Również A i B są odwrotnościami siebie, podczas gdy 1 , C , D i E są odpowiednio odwrotnościami samych siebie (odwrotność 1 to 1 , odwrotność C to C , odwrotność D to D , a odwrotność E oznacza E ).

Teraz możemy sprawdzić, czy (H, ∗) gdzie H = {1, A, B} jest podgrupą (G, ∗) . Informacje na temat zamknięcia znajdują się w poniższej tabeli:

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

w którym wszystkie możliwe pary elementów H pod * otrzymując człon w H .

Zespolenie nie wymaga kontroli, ponieważ elementy H są elementy G .

Tożsamość to 1 . To samo musi być z tożsamością grupy. Ponadto tożsamość w grupie musi być unikalna. (Czy możesz to udowodnić?)

Dla odwrotności sprawdź, czy odwrotnością A jest B , która jest członkiem H . Odwrotność B jest , który jest również członkiem H . Odwrotność 1 jest wciąż sama, co nie wymaga sprawdzania.

Zadanie

Opis

Biorąc pod uwagę skończoną grupę (G, ∗) , znajdź liczbę jej podgrup.

Wejście

Dla grupy (G, ∗) otrzymasz tablicę 2D o rozmiarze n × n , gdzie n jest liczbą elementów w G . Załóżmy, że indeks 0jest elementem tożsamości. Tablica 2D będzie reprezentować tabliczkę mnożenia. Na przykład dla powyższej grupy otrzymasz następującą tablicę 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]]

Na przykład możesz to zobaczyć 3 ∗ 1 = 5, ponieważ a[3][1] = 5gdzie ajest powyższa tablica 2D.

Uwagi:

• Możesz użyć 1-indeksowanej tablicy 2D.
• Wiersz i kolumnę tożsamości można pominąć.
• Możesz używać innych formatów według własnego uznania, ale muszą one być spójne.(tzn. możesz chcieć, aby ostatni indeks był identyczny itp.)

Wynik

Liczba dodatnia reprezentująca liczbę podgrup w grupie.

Na przykład dla powyższej grupy (H, ∗) jest podgrupą (G, ∗), ilekroć H =

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

Dlatego istnieje 6 podgrup, a twoje wyniki dla tego przykładu powinny być 6.

Poradnik

Możesz przeczytać artykuły, z którymi się łączyłem. Artykuły te zawierają twierdzenia o grupach i podgrupach, które mogą być dla Ciebie przydatne.

Punktacja

To jest golf golfowy . Odpowiedz z najniższą wygraną w liczbie bajtów.

Mathematica, 62 48 bajtów

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

Czysta funkcja oczekuje 1-indeksowanej tablicy 2D. Counts liczby Subsetsw Firstwierszu tablicy wejściowych, które są zamknięte w ramach operacji grupy. Ponieważ będzie to obejmować pusty zestaw, odejmujemy 1. Zauważ, że niepusty podzbiór skończonej grupy, który jest zamknięty w ramach operacji grupowej, jest w rzeczywistości podgrupą (i odwrotnie, z definicji).

Ściśle mówiąc, nie sprawdzam, czy podzbiór xjest zamknięty w ramach operacji grupowej, ograniczam tabliczkę mnożenia do podzbioru xi sprawdzam, czy zawiera on dokładnie elementy x. Wyraźnie oznacza to, że xjest zamknięty w odniesieniu do operacji grupowej. I odwrotnie, każda podgrupa xbędzie zawierać, 1a zatem xbędzie podzbiorem elementów pojawiających się w ograniczonej tablicy mnożenia, a ponieważ xjest zamknięta w ramach operacji grupowej, musi być równa x.

Haskell , 79 bajtów

Zasadniczo port metody Mathematica ngenisis. (Z wyjątkiem, że korzystam z tablic indeksowanych 0).

cpobiera listę Ints i zwraca liczbę całkowitą.

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

Wypróbuj online!

Zakłada się, że Ints są ponumerowane tak samo jak wiersze (listy zewnętrzne) i kolumny pokazujące ich pomnożenie. Zatem, ponieważ 0 to tożsamość, pierwsza kolumna jest taka sama jak indeksy wierszy. Pozwala to na użycie wpisów z pierwszej kolumny do zbudowania podzbiorów.

Jak to działa

• c jest główną funkcją.
• g to tablica grupowa jako lista list.
• ljest podzbiorem elementów. Lista podzbiorów jest zbudowana w następujący sposób:
  • foldr(\r->([id,(r!!0:)]<*>))[[]]gskłada funkcję nad wierszami g.
  • rjest wierszem g, którego pierwszy (0) element jest wyodrębniany jako element, który może być włączony ( (r!!0:)) lub nie ( id).
  • <*> łączy wybory dla tego wiersza z następującymi.
• and[g!!x!!y`elem`l|x<-l,y<-l]sprawdza dla każdej pary elementów, lczy jest ich wielokrotność l.
• sum[1|...]-1 zlicza podzbiory, które pomyślnie przejdą test, z wyjątkiem jednego pustego podzbioru.

Galaretka , 17 16 bajtów

1 bajt dzięki 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.

Wypróbuj online! (1-indeksowany)

Python 2, 297 215 bajtów

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

Wypróbuj online

Ten program działa bez przykładowej grupy ==T[x][y], ale wciąż jestem pewien, że jest to konieczne.

Edycja: Teraz zakłada się, że element tożsamości G jest zawsze pierwszy.

Nie golfowany:

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

Niegolfowane TIO

Ujemne elementy grupy można obsługiwać bezpłatnie, zmieniając -1na ''.