Grup

Dalam aljabar abstrak, grup adalah tupel $(G,\ast)$ , di mana $G$ adalah himpunan dan $\ast$ adalah fungsi $G\times G\rightarrow G$ sedemikian rupa sehingga berlaku sebagai berikut:

• Untuk semua $x, y, z$ dalam $G$ , $(x\ast y)\ast z=x\ast(y\ast z)$ .

• Ada elemen $e$ di $G$ sehingga untuk semua $x$ di $G$ , $x\ast e=x$ .

• Untuk setiap $x$ dalam $G$ , ada elemen $y$ di $G$ sehingga $x\ast y=e$ .

The rangka dari kelompok $(G,\ast)$ didefinisikan sebagai jumlah elemen dari $G$ .

Untuk setiap bilangan bulat positif , ada setidaknya satu kelompok pesanan n . Sebagai contoh, ( C n , + n ) adalah kelompok seperti itu, di mana C n = { 0 , . . . , n - 1 } dan x + n y = ( x + y $n$$n$$(C_n,+_n)$$C_n=\{0,...,n-1\}$ .$x+_ny=(x+y)\mod n$

Kelompok isomorfik

Biarkan dan tentukan ∗ oleh x ∗ y = ( x × y $G:=\{1,2\}$$\ast$ . Kemudian 1 ∗ 1 = 1 = 2 ∗ 2 dan 1 ∗ 2 = 2 = 2 ∗ $x\ast y=(x\times y)\mod3$$1\ast1=1=2\ast2$$1\ast2=2=2\ast1$ .

Demikian juga, dan 0 + 2 1 = 1 = 1 + 2$0+_20=0=1+_21$$0+_21=1=1+_20$ .

Meskipun elemen dan operasi grup dan ( C 2 , + 2$(G,\ast)$$(C_2,+_2)$ memiliki nama yang berbeda, grup memiliki struktur yang sama.

Dua kelompok dan ( G 2 , ∗ 2 ) dikatakan isomorfik jika ada penambangan ϕ : G 1 → G 2 sedemikian rupa sehingga ϕ ( x ∗ 1 y ) = ϕ ( x ) ∗ 2 ϕ ( y ) untuk semua x , y dalam 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$

Tidak semua kelompok dengan urutan yang sama isomorfik. Sebagai contoh, kelompok Klein adalah sekelompok order 4 yang tidak isomorfis ke .$(C_4,+_4)$

Tugas

Tulis program atau fungsi yang menerima bilangan bulat non-negatif n sebagai input dan mencetak atau mengembalikan jumlah kelompok urutan non-isomorfik n .

Uji kasus

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

(diambil dari OEIS A000001 )

Aturan tambahan

• Tidak ada batasan waktu eksekusi atau penggunaan memori.

• Built-in yang meremehkan tugas ini, seperti Mathematica FiniteGroupCount, tidak diperbolehkan.

• Aturan standar kode-golf berlaku.

CJam, 189 187 byte

Yang ini akan sulit dijelaskan ... Kompleksitas waktu dijamin 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=},,}{!!}?

Jika Anda cukup berani, cobalah secara online . Di laptop jelek saya, saya bisa mendapatkan hingga 6 dengan juru bahasa Java atau 5 di juru bahasa online.

Penjelasan

Saya tidak memiliki latar belakang matematika yang besar (baru lulus SMA, mulai CS di universitas minggu depan). Jadi bersabarlah jika saya melakukan kesalahan, nyatakan yang jelas, atau lakukan hal-hal dengan cara yang sangat tidak efisien.

Pendekatan saya adalah kekuatan kasar, meskipun saya mencoba membuatnya sedikit lebih pintar. Langkah-langkah utamanya adalah:

1. Hasilkan semua operan yang mungkin ∗ untuk sekelompok urutan n (yaitu, hitung semua kelompok pesanan n );
2. Hasilkan semua kemungkinan bijections φ antara dua kelompok urutan n ;
3. Dengan menggunakan hasil dari langkah 1 dan 2, tentukan semua isomorfisme antara dua kelompok orde n ;
4. Dengan menggunakan hasil dari langkah 3, hitung jumlah kelompok hingga isomorfisma.

Sebelum melihat bagaimana setiap langkah dilakukan, mari kita buat beberapa kode sepele:

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)

Algoritma berikut tidak bekerja dengan benar dengan n <4 , kasing dari 0 ke 3 ditangani dengan negasi ganda.

Mulai sekarang, elemen-elemen grup akan ditulis sebagai {1, a, b, c, ...} , di mana 1 adalah elemen identitas. Dalam implementasi CJam, elemen yang sesuai adalah {0, 1, 2, 3, ...} , di mana 0 adalah elemen identitas.

Mari kita mulai dari langkah 1. Menulis semua operator yang memungkinkan untuk sekelompok pesanan n setara dengan menghasilkan semua tabel Cayley n × n yang valid . Baris dan kolom pertama sepele: keduanya {1, a, b, c, ...} (kiri-ke-kanan, atas-ke-bawah).

      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

Mengetahui bahwa tabel Cayley juga merupakan kotak Latin yang diperkecil (karena properti pembatalan) memungkinkan untuk menghasilkan tabel yang mungkin baris-demi-baris. Mulai dari baris kedua (indeks 1), kami menghasilkan semua permutasi unik untuk baris itu, menjaga kolom pertama tetap pada nilai indeks.

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

Tidak semua permutasi itu valid, tentu saja: setiap baris dan kolom harus berisi semua elemen tepat satu kali. Blok filter digunakan untuk tujuan ini (nilai kebenaran menjaga permutasi, yang salah menghapusnya):

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

Perhatikan bahwa saya memfilter di dalam loop generasi: ini membuat kode sedikit lebih lama (dibandingkan dengan generasi berbeda dan pemfilteran), tetapi sangat meningkatkan kinerja. Jumlah permutasi dari satu set ukuran n adalah n! , jadi solusi yang lebih pendek tentu membutuhkan banyak memori dan waktu.

Daftar tabel Cayley yang valid adalah langkah bagus untuk menghitung operator, tetapi sebagai struktur 2D, ia tidak dapat memeriksa asosiatif, yang merupakan properti 3D. Jadi langkah selanjutnya adalah menyaring fungsi non-asosiatif.

{                                 }, 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]

Fiuh! Banyak pekerjaan, tetapi sekarang kami telah menghitung semua kelompok pesanan n (atau lebih baik, operasi di atasnya - tetapi set tetap, jadi itu adalah hal yang sama). Langkah selanjutnya: temukan isomorfisma. Isomorfisme adalah suatu ikatan antara dua kelompok tersebut sehingga φ (x ∗ y) = φ (x) ∗ φ (y) . Membuat bijections di CJam itu sepele: Ne!akan melakukannya. Bagaimana kita memeriksanya? Solusi saya mulai dari dua salinan tabel Cayley selama x ∗ y . Pada satu salinan, φ diterapkan ke semua elemen, tanpa menyentuh urutan baris atau kolom. Ini menghasilkan tabel untuk φ (x ∗ y) . Di sisi lain elemen dibiarkan apa adanya, tetapi baris dan kolom dipetakan melalui φ . Yaitu, baris / kolom x menjadi baris / kolomφ (x) . Ini menghasilkan tabel untuk φ (x) ∗ φ (y) . Sekarang kita memiliki dua tabel, kita hanya harus membandingkannya: jika mereka sama, kita telah menemukan isomorfisme.

Tentu saja, kita juga perlu membuat pasangan kelompok untuk menguji isomorfisme. Kami membutuhkan semua 2 kombinasi grup. Sepertinya CJam tidak memiliki operator untuk kombinasi. Kita dapat menghasilkan mereka dengan mengambil setiap grup dan menggabungkannya hanya dengan elemen yang mengikutinya dalam daftar. Fakta menyenangkan: jumlah 2-kombinasi adalah n × (n - 1) / 2 , yang juga merupakan jumlah dari n - 1 bilangan asli. Angka tersebut disebut angka segitiga: coba algoritme di atas kertas, satu baris per elemen tetap, dan Anda akan tahu alasannya.

: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

Kode di atas memperbaiki elemen pertama dari pasangan, L [X] , dan menggabungkannya dengan kelompok lain (sebut saja masing-masing dari mereka Y ). Ini melewati pasangan ke blok uji isomorfisma yang akan saya tunjukkan sebentar lagi. Blok memberikan kembali daftar nilai dari Y yang L [X] adalah isomorfik ke Y . Kemudian L [X] ditambahkan ke daftar ini. Sebelum memahami mengapa daftar diatur sedemikian rupa, mari kita lihat tes isomorfisme:

\_@                                      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

Hebat, sekarang kami memiliki daftar set seperti [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . Idenya di sini adalah, dengan properti transitif, jika ada dua set yang memiliki setidaknya satu elemen yang sama maka semua kelompok dalam dua set adalah isomorfik. Mereka dapat dikumpulkan menjadi satu set. Karena L [X] tidak akan pernah muncul dalam kombinasi yang dihasilkan oleh L [X + ...] , setelah menggabungkan setiap rangkaian isomorfisma akan memiliki satu elemen unik. Jadi, untuk mendapatkan jumlah isomorfisma, cukup untuk menghitung berapa banyak kelompok yang muncul tepat sekali dalam semua kelompok kelompok isomorfik. Untuk melakukan ini, saya membuka bungkusan set sehingga terlihat seperti [L [0], Y1, Y2, ..., L [1], Y1, ...] , urutkan daftar untuk membuat kelompok dari kelompok yang sama dan akhirnya RLE-encode itu.

:~            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

Itu saja, semuanya.

CJam, 73 byte

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

Kompleksitas waktu dari kode di atas lebih buruk daripada O (n! ^N ) .

Input n = 4 sudah terlalu banyak untuk penerjemah online .

Menggunakan penerjemah Java , input n = 5 dapat dimungkinkan, jika Anda memiliki cukup RAM dan kesabaran.

Menemukan kelompok

Diberikan grup (G, ∗) dari pesanan n , kita dapat memilih penambangan acak φ: G -> C _n sedemikian rupa sehingga φ (e) = 0 .

φ akan menjadi isomorfisma (G, ∗) dan (C _n , ∗ ') jika kita mendefinisikan ∗' oleh x ∗ 'y = φ (φ ^-1 (x) ∗ φ ^-1 (y)) .

Ini berarti bahwa cukup untuk mempelajari semua operator grup dalam C _n sehingga 0 adalah elemen netral.

Kami akan mewakili operator grup ∗ di C _n dengan array T persegi panjang dimensi n × n sehingga T [x] [y] = x ∗ y .

Untuk menghasilkan sebuah array, kita bisa mulai dengan memilih permutasi dari C _n untuk masing-masing nya n baris.

Dengan cara ini, 0 akan ada di semua baris (tetapi tidak harus semua kolom ), yang berarti bahwa kondisi ketiga (keberadaan invers) akan terpenuhi, apa pun e .

Kita bisa memperbaiki e = 0 dengan mengharuskan bahwa yang pertama kolom dari T sama dengan C _n . Secara khusus, kondisi kedua (keberadaan elemen netral) akan berlaku.

Untuk memverifikasi bahwa T sesuai dengan operator grup, yang perlu dilakukan hanyalah memverifikasi bahwa kondisi pertama (asosiatif) berlaku. Ini dapat dilakukan secara mendalam dengan memeriksa bahwa T [T [x] [y]] [z] == T [x] [T [y] [z]] untuk semua x, y, z dalam C _n .

Menghitung kelompok non-isomorfik

Metode di atas untuk menemukan kelompok akan menghasilkan beberapa kelompok isomorfik. Daripada mengidentifikasi mana yang isomorfik, kami menghasilkan keluarga semua kelompok isomorfik untuk masing-masing dari mereka.

Hal ini dapat dilakukan dengan mengulangi semua biopsi ject : C _n -> C _n , dan menentukan array yang terkait T array , yang didefinisikan oleh T by [x] [y] = φ ^-1 (T [φ (x)] [φ (y )]) .

Yang tersisa untuk dilakukan adalah menghitung jumlah keluarga yang berbeda.

Apa yang dilakukan kode

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 byte

• Disimpan delapan byte berkat Dennis .

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)

Cobalah online!

Menggunakan kesetaraan antara jumlah subkelompok urutan non-isomorfik $n$ dari $\ \Sigma_n$ dan jumlah kelas ekivalensi isomorfik dari kelompok tatanan terbatas $n$.

Tautan ke versi verbose .