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 3 (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 0
jest 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] = 5
gdzie a
jest 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.
źródło
0
element tożsamości, to mylące jest, gdy operator jest opisywany jako mnożenie ...Odpowiedzi:
Mathematica,
6248 bajtówCzysta funkcja oczekuje 1-indeksowanej tablicy 2D.
Count
s liczbySubsets
wFirst
wierszu tablicy wejściowych, które są zamknięte w ramach operacji grupy. Ponieważ będzie to obejmować pusty zestaw, odejmujemy1
. 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
x
jest zamknięty w ramach operacji grupowej, ograniczam tabliczkę mnożenia do podzbiorux
i sprawdzam, czy zawiera on dokładnie elementyx
. Wyraźnie oznacza to, żex
jest zamknięty w odniesieniu do operacji grupowej. I odwrotnie, każda podgrupax
będzie zawierać,1
a zatemx
będzie podzbiorem elementów pojawiających się w ograniczonej tablicy mnożenia, a ponieważx
jest zamknięta w ramach operacji grupowej, musi być równax
.źródło
Haskell , 79 bajtów
Zasadniczo port metody Mathematica ngenisis. (Z wyjątkiem, że korzystam z tablic indeksowanych 0).
c
pobiera listęInt
s i zwraca liczbę całkowitą.Wypróbuj online!
Zakłada się, że
Int
s 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.l
jest podzbiorem elementów. Lista podzbiorów jest zbudowana w następujący sposób:foldr(\r->([id,(r!!0:)]<*>))[[]]g
składa funkcję nad wierszamig
.r
jest wierszemg
, 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,l
czy jest ich wielokrotnośćl
.sum[1|...]-1
zlicza podzbiory, które pomyślnie przejdą test, z wyjątkiem jednego pustego podzbioru.źródło
Galaretka ,
1716 bajtów1 bajt dzięki ETHproductions (
LR → J
)Wypróbuj online! (1-indeksowany)
źródło
J
zamiastLR
zapisać bajt :-)Python 2,
297215 bajtówWypró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:
Niegolfowane TIO
Ujemne elementy grupy można obsługiwać bezpłatnie, zmieniając
-1
na''
.źródło
0
, a nie o indeks.