Grupy

W algebrze abstrakcyjnej grupa jest krotką $(G,\ast)$ , gdzie $G$ jest zbiorem, a $\ast$ jest funkcją $G\times G\rightarrow G$ tak że następujące:

• Dla wszystkich $x, y, z$ w $G$ , $(x\ast y)\ast z=x\ast(y\ast z)$ .

• Istnieje element $e$ na $G$ , że dla wszystkich $x$ w $G$ , $x\ast e=x$ .

• Dla każdego $x$ , w $G$ , istnieje element $y$ na $G$ w taki sposób, $x\ast y=e$ .

Kolejność grupy $(G,\ast)$ jest zdefiniowana jako liczba elementów $G$ .

Dla każdej ściśle dodatniej liczby całkowitej istnieje co najmniej jedna grupa rzędu n . Na przykład, ( C, N , + n ) jest taką grupą, w której C n = { 0 , . . . , n - 1 } i x + n y = ( x + y $n$$n$$(C_n,+_n)$$C_n=\{0,...,n-1\}$ .$x+_ny=(x+y)\mod n$

Grupy izomorficzne

Niech i zdefiniuj ∗ przez x ∗ y = ( x × y $G:=\{1,2\}$$\ast$ . Następnie 1 ∗ 1 = 1 = 2 ∗ 2 i 1 ∗ 2 = 2 = 2 ∗ 1 .$x\ast y=(x\times y)\mod3$$1\ast1=1=2\ast2$$1\ast2=2=2\ast1$

Podobnie i 0 + 2 1 = 1 = 1 + 2 0 .$0+_20=0=1+_21$$0+_21=1=1+_20$

Chociaż elementy i operacje grup i ( C 2 , + 2 ) mają różne nazwy, grupy mają tę samą strukturę.$(G,\ast)$$(C_2,+_2)$

Mówi się, że dwie grupy i ( G 2 , ∗ 2 ) są izomorficzne, jeśli istnieje bijection ϕ : G 1 → G 2 taki, że ϕ ( x ∗ 1 y ) = ϕ ( x ) ∗ 2 ϕ ( y ) dla wszystkich x , y w G 1 .$(G_1,\ast_1)$$(G_2,\ast_2)$$\phi:G_1\rightarrow G_2$$\phi(x\ast_1y)=\phi(x)\ast_2\phi(y)$$x,y$$G_1$

Nie wszystkie grupy tego samego rzędu są izomorficzne. Na przykład grupa Kleina jest grupą rzędu 4, która nie jest izomorficzna w stosunku do .$(C_4,+_4)$

Zadanie

Napisz program lub funkcję, która przyjmuje nieujemną liczbę całkowitą n jako dane wejściowe i wypisuje lub zwraca liczbę nieizomorficznych grup rzędu n .

Przypadki testowe

Input   Output
0       0
1       1
2       1
3       1
4       2
5       1
6       2
7       1
8       5
9       2
10      2
11      1
12      5
13      1
14      2
15      1
16      14
17      1
18      5
19      1
20      5

(pochodzi z OEIS A000001 )

Dodatkowe zasady

• Nie ma żadnych limitów czasu wykonania ani użycia pamięci.

• Wbudowane, które trywializują to zadanie, takie jak Mathematica FiniteGroupCount, nie są dozwolone.

• Obowiązują standardowe zasady gry w golfa .

CJam, 189 187 bajtów

Trudno to wytłumaczyć ... Gwarantowana jest złożoność czasu O(scary).

qi:N_3>{,aN*]N({{:L;N,X)-e!{X)_@+L@@t}%{X2+<z{_fe=:(:+}%:+!},}%:+}fX{:G;N3m*{_~{G@==}:F~F\1m>~F\F=}%:*},:L,({LX=LX)>1$f{\_@a\a+Ne!\f{\:M;~{M\f=z}2*\Mff==}:|{;}|}\a+}fX]:~$e`{0=1=},,}{!!}?

Jeśli masz dość odwagi, wypróbuj go online . Na moim kiepskim laptopie mogę uzyskać do 6 przy pomocy interpretera Java lub 5 przy tłumaczu online.

Wyjaśnienie

Nie mam dużego doświadczenia matematycznego (właśnie skończyłem szkołę średnią, zaczynając CS na uniwersytecie w przyszłym tygodniu). Więc miejcie mnie przy sobie, jeśli popełniam błędy, stwierdzam to, co oczywiste lub robię rzeczy w okropnie nieskuteczny sposób.

Moje podejście to brutalna siła, choć starałem się uczynić to trochę bardziej sprytnym. Główne kroki to:

1. Wygeneruj wszystkie możliwe operandy ∗ dla grupy rzędu n (tj. Wylicz wszystkie grupy rzędu n );
2. Wygeneruj wszystkie możliwe wstrząsy φ między dwiema grupami rzędu n ;
3. Wykorzystując wyniki z kroków 1 i 2, określ wszystkie izomorfizmy między dwiema grupami rzędu n ;
4. Wykorzystując wynik z kroku 3, policz liczbę grup aż do izomorfizmu.

Zanim spojrzymy na to, jak wykonuje się każdy krok, usuńmy z tego jakiś trywialny kod:

qi:N_             e# Get input as integer, store in N, make a copy
     3>{...}    ? e# If N > 3, do... (see below)
            {!!}  e# Else, push !!N (0 if N=0, 1 otherwise)

Poniższy algorytm nie działa poprawnie dla n <4 , przypadki od 0 do 3 są obsługiwane z podwójną negacją.

Odtąd elementy grupy będą zapisywane jako {1, a, b, c, ...} , gdzie 1 to element tożsamości. W implementacji CJam odpowiednimi elementami są {0, 1, 2, 3, ...} , gdzie 0 to element tożsamości.

Zacznijmy od kroku 1. Zapisanie wszystkich możliwych operatorów dla grupy rzędu n jest równoważne wygenerowaniu wszystkich prawidłowych tabel Cayley n × n . Pierwszy wiersz i kolumna są trywialne: oba są {1, a, b, c, ...} (od lewej do prawej, od góry do dołu).

      e# N is on the stack (duplicated before the if)
,a    e# Generate first row [0 1 2 3 ...] and wrap it in a list
  N*  e# Repeat row N times (placeholders for next rows)
    ] e# Wrap everything in a list
      e# First column will be taken care of later

Wiedza, że ​​tabela Cayleya jest również zmniejszonym kwadratem łacińskim (ze względu na właściwość anulowania) pozwala generować możliwe tabele wiersz po rzędzie. Zaczynając od drugiego wiersza (indeks 1), generujemy wszystkie unikalne permutacje dla tego wiersza, utrzymując pierwszą kolumnę ustawioną na wartość indeksu.

N({                                 }fX e# For X in [0 ... N-2]:
   {                            }%      e#   For each table in the list:
    :L;                                 e#     Assign the table to L and pop it off the stack
       N,                               e#     Push [0 ... N-1]
         X)                             e#     Push X+1
           -                            e#     Remove X+1 from [0 ... N-1]
            e!                          e#     Generate all the unique permutations of this list
              {         }%              e#     For each permutation:
               X)_                      e#       Push two copies of X+1
                  @+                    e#       Prepend X+1 to the permutation
                    L@@t                e#       Store the permutation at index X+1 in L
                          {...},        e#     Filter permutations (see below)
                                  :+    e#   Concatenate the generated tables to the table list

Oczywiście nie wszystkie te permutacje są ważne: każdy wiersz i kolumna musi zawierać wszystkie elementy dokładnie jeden raz. W tym celu stosuje się blok filtra (prawdziwa wartość utrzymuje permutację, a fałsz ją usuwa):

X2+                 e# Push X+2
   <                e# Slice the permutations to the first X+2 rows
    z               e# Transpose rows and columns
     {        }%    e# For each column:
      _fe=          e#   Count occurences of each element
          :(        e#   Subtract 1 from counts
            :+      e#   Sum counts together
                :+  e# Sum counts from all columns together
                  ! e# Negate count sum:
                    e#   if the sum is 0 (no duplicates) the permutation is kept
                    e#   if the sum is not zero the permutation is filtered away

Zauważ, że filtruję wewnątrz pętli generacyjnej: powoduje to, że kod jest nieco dłuższy (w porównaniu do odrębnego generowania i filtrowania), ale znacznie poprawia wydajność. Liczba permutacji zestawu wielkości n wynosi n! , więc krótsze rozwiązanie wymagałoby dużo pamięci i czasu.

Lista prawidłowych tabel Cayleya jest wielkim krokiem w kierunku wyliczenia operatorów, ale ponieważ jest strukturą 2D, nie może sprawdzić powiązania, które jest właściwością 3D. Kolejnym krokiem jest odfiltrowanie funkcji niepowiązanych.

{                                 }, e# For each table, keep table if result is true:
 :G;                                 e#   Store table in G, pop it off the stack
    N3m*                             e#   Generate triples [0 ... N-1]^3
        {                     }%     e#   For each triple [a b c]:
         _~                          e#     Make a copy, unwrap top one
           {    }:F                  e#     Define function F(x,y):
            G@==                     e#       x∗y (using table G)
                   ~F                e#     Push a∗(b∗c)
                     \1m>            e#     Rotate triple right by 1
                         ~           e#     Unwrap rotated triple
                          F\F        e#     Push (a∗b)∗c
                             =       e#     Push 1 if a∗(b∗c) == (a∗b)∗c (associative), 0 otherwise
                                :*   e#   Multiply all the results together
                                     e#   1 (true) only if F was associative for every [a b c]

Uff! Dużo pracy, ale teraz wyliczyliśmy wszystkie grupy rzędu n (lub lepiej, operacje na nim - ale zestaw jest ustalony, więc to samo). Następny krok: znajdź izomorfizmy. Izomorfizm to zderzenie między dwiema tymi grupami, tak że φ (x ∗ y) = φ (x) ∗ φ (y) . Generowanie tych bijectów w CJam jest banalne: Ne!zrobi to. Jak możemy to sprawdzić? Moje rozwiązanie zaczyna się od dwóch kopii tabeli Cayleya dla x ∗ y . Na jednym egzemplarzu φ jest stosowany do wszystkich elementów, bez zmiany kolejności wierszy lub kolumn. To generuje tabelę dla φ (x ∗ y) . Z drugiej strony elementy pozostały takie, jakie są, ale wiersze i kolumny są odwzorowane przez φ . To znaczy wiersz / kolumnax staje się wierszem / kolumną φ (x) . To generuje tabelę dla φ (x) ∗ φ (y) . Teraz, gdy mamy dwie tabele, musimy je po prostu porównać: jeśli są takie same, znaleźliśmy izomorfizm.

Oczywiście musimy również wygenerować pary grup do przetestowania izomorfizmu. Potrzebujemy wszystkich 2 kombinacji grup. Wygląda na to, że CJam nie ma operatora dla kombinacji. Możemy je wygenerować, biorąc każdą grupę i łącząc ją tylko z następującymi po niej elementami na liście. Ciekawostka: liczba 2 kombinacji to n × (n - 1) / 2 , co jest również sumą pierwszych n - 1 liczb naturalnych. Takie liczby nazywane są liczbami trójkątnymi: wypróbuj algorytm na papierze, jeden rząd na stały element, a zobaczysz dlaczego.

:L                          e# List of groups is on stack, store in L
  ,(                        e# Push len(L)-1
    {                  }fX  e# For X in [0 ... len(L)-2]:
     LX=                    e#   Push the group L[X]
        LX)>                e#   Push a slice of L excluding the first X+1 elements
            1$              e#   Push a copy of L[X]
              f{...}        e#   Pass each [L[X] Y] combination to ... (see below)
                            e#   The block will give back a list of Y for isomorphic groups
                    \a+     e#   Append L[X] to the isomorphic groups
                          ] e# Wrap everything in a list

Powyższy kod naprawia pierwszy element pary, L [X] , i łączy go z innymi grupami (nazwijmy każdy z tych Y ). Przekazuje parę do bloku testowego izomorfizmu, który zaraz pokażę. Blok oddaje listę wartości Y dla których L [X] jest izomorficzny Y . Następnie L [X] jest dołączany do tej listy. Zanim zrozumiemy, dlaczego listy są ustawione w taki sposób, spójrzmy na test izomorficzny:

\_@                                      e# Push a copy of Y
   a\a+                                  e# L[X] Y -> [L[X] Y]
       Ne!                               e# Generate all bijective mappings
          \f{                    }       e# For each bijection ([L[X] Y] extra parameter):
             \:M;                        e#   Store the mapping in M, pop it off the stack
                 ~                       e#   [L[X] Y] -> L[X] Y
                  {     }2*              e#   Repeat two times (on Y):
                   M\f=                  e#     Map rows (or transposed columns)
                       z                 e#     Transpose rows and columns
                                         e#     This generates φ(x) ∗ φ(y)
                           \Mff=         e#   Map elements of L[X], generates φ(x ∗ y)
                                =        e#   Push 1 if the tables are equal, 0 otherwise
                                  :|     e#   Push 1 if at least a mapping was isomorphic, 0 otherwise
                                    {;}| e#   If no mapping was isomorphic, pop the copy of Y off the stack

Świetnie, teraz mamy listę zestawów takich jak [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . Chodzi o to, że według własności przechodnich, jeśli dowolne dwa zestawy mają co najmniej jeden wspólny element, wówczas wszystkie grupy w dwóch zestawach są izomorficzne. Można je agregować w jeden zestaw. Ponieważ L [X] nigdy nie pojawi się w kombinacjach generowanych przez L [X + ...] , po agregacji każdy zestaw izomorfizmów będzie miał jeden unikalny element. Aby więc uzyskać liczbę izomorfizmów, wystarczy policzyć, ile grup pojawia się dokładnie raz we wszystkich zestawach grup izomorficznych. Aby to zrobić, rozpakowuję zestawy, aby wyglądały jak [L [0], Y1, Y2, ..., L [1], Y1, ...] , posortuj listę, aby utworzyć klastry tej samej grupy i na końcu Kodowanie RLE.

:~            e# Unwrap sets of isomorphic groups
  $           e# Sort list
   e`         e# RLE-encode list
     {    },  e# Filter RLE elements:
      0=      e#   Get number of occurrences
        1=    e#   Keep element if occurrences == 1
            , e# Push length of filtered list
              e# This is the number of groups up to isomorphism

To wszystko, ludzie.

CJam, 73 bajty

0ri:Re!Rm*{:Tz0=R,=[R,Te_]m!{~ff{T==}e_}/=&},{:T,e!{:PPff{T==P#}}%$}%Q|,+

Złożoność czasowa powyższego kodu jest gorsza niż O (n! ^N ) .

Wartość wejściowa n = 4 jest już za duża dla tłumacza online .

Używając interpretera Java , wejście n = 5 może być możliwe, jeśli masz wystarczająco dużo pamięci RAM i cierpliwości.

Znajdowanie grup

Biorąc pod uwagę grupę (G, ∗) rzędu n , możemy wybrać dowolny bijection φ: G -> C _n taki, że φ (e) = 0 .

φ stanie się izomorfizmem (G, ∗) i (C _n , ∗ '), jeśli zdefiniujemy ∗' przez x ∗ 'y = φ (φ ^-1 (x) ∗ φ ^-1 (y)) .

Oznacza to, że wystarczy zbadać wszystkich operatorów grup w C _n , aby 0 było elementem neutralnym.

Będziemy reprezentować operator grupy ∗ w C _n przez prostokątny układ T o wymiarach n × n taki, że T [x] [y] = x ∗ y .

Aby wygenerować taką tablicę, możemy zacząć od wybrania permutacji C _n dla każdego z jej n wierszy.

W ten sposób, 0 będzie obecny we wszystkich rzędach (ale niekoniecznie wszystkich kolumnach ), co oznacza, że trzeci warunek (istnienie odwrotności) zostaną spełnione, niezależnie e może być.

Można ustalić e = 0 , wymagając, że pierwsza kolumna z T jest równy C _n . W szczególności utrzyma się drugi warunek (istnienie elementu neutralnego).

Aby sprawdzić, czy T odpowiada operatorowi grupy, wystarczy sprawdzić, czy spełniony jest pierwszy warunek (asocjatywność). Można to zrobić wyczerpująco, sprawdzając, czy T [T [x] [y]] [z] == T [x] [T [y] [z]] dla wszystkich x, y, z w C _n .

Zliczanie grup nieizomorficznych

Powyższa metoda znajdowania grup da pewne grupy izomorficzne. Zamiast identyfikować, które z nich są izomorficzne, generujemy rodzinę wszystkich grup izomorficznych dla każdej z nich.

Można tego dokonać, iterując wszystkie bijectie φ: C _n -> C _n i określając powiązaną tablicę Tφ , zdefiniowaną przez Tφ [x] [y] = φ ^-1 (T [φ (x)] [φ (y )]) .

Pozostało tylko zliczyć liczbę różnych rodzin.

Co robi kod

0         e# Push 0. For input 0, the remaining code will crash, leaving
          e# this 0 on the stack.
ri:R      e# Read an integer from STDIN and save it in R.
e!        e# Push all permutations of [0 ... R-1].
Rm*       e# Push all arrays of 6 permutations of [0 ... R-1].
{         e# Filter; for each array:
  :T      e#   Save it in T.
  z0=R,=  e#   Check if the first column equals [0 ... R-1].
  [R,Te_] e#   Push [0 ... R-1] and a flattened T.
  m!{     e#   For both pairs (any order):
    ~     e#     Unwrap the pair.
    ff{   e#     For each X in the first: For each Y in the second:
      T== e#       Push T[X][Y].
    }     e#
  }/      e#
  =       e#   Check for equality, i.e., associativity.
  &       e#   Bitwise AND with the previous Boolean
},        e# Keep T iff the result was truthy.
{         e# For each kept array:
  :T      e#   Save it in T
  ,e!     e#   Push all permutations of [0 ... R-1].
  {       e#   For each permutation:
    :PP   e#     Save it in P. Push a copy.
    ff{   e#     For each X in P: For each Y in P:
      T== e#       Push T[X][Y].
      P#  e#       Find its index in P.
    }     e#
  }%      e#
  $       e#   Sort the results.
}%        e#
Q|,       e# Deduplicate and count.
+         e# Add the result to the 0 on the stack.

Python 2 , 515 507 bajtów

• Zaoszczędzono osiem bajtów dzięki Dennisowi .

def F(n):
 def f(k,*s):n==len(set(s))and S.add(s);{k and f(~-k,j,*s)for j in I}
 def c(k,*G):k and{s in G or c(~-k,s,*G)for s in S}or(I in G)&all((o(x,y)in G)&any(I==o(z,x)for z in G)for x in G for y in G)and A.add(G)
 S=set();A=S-S;I=tuple(range(n));o=lambda x,y:tuple(y[x[j]]for j in I);i=lambda G,H:any(all(o(H[B[i]],H[B[j]])==H[B[[k for k in I if G[k]==o(G[i],G[j])][0]]]for i in I for j in I)for B in S);f(n);c(n);K=list(A);[G in K and{G!=H and i(G,H)and K.remove(H)for H in K}for G in A];return len(K)

Wypróbuj online!

Wykorzystanie równoważności między liczbą nieizomorficznych podgrup rzędu $n$ z $\ \Sigma_n$ oraz liczba izomorficznych klas równoważności skończonych grup rzędu $n$.

Link do pełnej wersji .