CJam, 189 187 바이트

이것은 설명하기 어려울 것입니다 … 시간 복잡성은 보장됩니다 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=},,}{!!}?

당신이 용감하다면 온라인으로 사용해보십시오 . 내 엉터리 노트북에서 Java 인터프리터로 최대 6 개 또는 온라인 인터프리터로 최대 5 개를 얻을 수 있습니다.

설명

나는 큰 수학 배경이 없습니다 (다음 주 uni에서 CS를 시작하여 고등학교를 마쳤습니다). 내가 실수를하거나 명백하게 말하거나 끔찍한 방법으로 일을하면 나와 함께 견뎌내십시오.

좀 더 영리하게 만들려고했지만 내 접근 방식은 무차별적인 힘입니다. 주요 단계는 다음과 같습니다.

1. 가능한 모든 피연산자 생성 * 차수의 그룹을 N (즉, 순서의 모든 그룹 열거 N을 );
2. 두 그룹의 차수 n 사이에 가능한 모든 jection φ를 생성합니다 .
3. 단계 1과 2의 결과를 사용하여 차수 n의 두 그룹 사이의 모든 동형을 결정하십시오 .
4. 3 단계의 결과를 사용하여 동형까지 그룹 수를 계산합니다.

각 단계의 수행 방식을 살펴보기 전에 다음과 같은 간단한 코드를 작성해 보겠습니다.

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)

다음 알고리즘은 n <4 에서 올바르게 작동하지 않으며 0에서 3까지의 경우는 이중 부정으로 처리됩니다.

이제부터 그룹의 요소는 {1, a, b, c, …}로 작성 되며 여기서 1 은 ID 요소입니다. CJam 구현에서 해당 요소는 {0, 1, 2, 3, …} 이며 여기서 0 은 ID 요소입니다.

하자의 순서의 그룹에 대한 가능한 모든 사업자를 작성하는 1 단계부터 시작 n은 유효한 모든 생성과 동일 N × N 케일리 테이블을 . 첫 번째 행과 열은 간단합니다. 둘 다 {1, a, b, c, …}입니다 (왼쪽에서 오른쪽으로, 위에서 아래로).

      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

Cayley 테이블이 라틴 속성으로 인해 (취소 특성으로 인해) 줄어듦 으로써 가능한 테이블을 행 단위로 생성 할 수 있습니다. 두 번째 행 (인덱스 1)부터 시작하여 해당 행에 대한 모든 순열 을 생성 하고 첫 번째 열은 인덱스 값으로 고정합니다.

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

물론 이러한 순열이 모두 유효한 것은 아닙니다. 각 행과 열에는 모든 요소가 정확히 한 번만 포함되어야합니다. 필터 블록은 이러한 목적으로 사용됩니다 (진실한 값은 순열을 유지하고 허위 값은 제거합니다).

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

생성 루프 내에서 필터링 중입니다. 이렇게하면 코드가 약간 길어지고 (고유 생성 및 필터링에 비해) 성능이 크게 향상됩니다. 크기 n 세트의 순열 수 는 n입니다! 따라서 더 짧은 솔루션은 많은 메모리와 시간이 필요합니다.

유효한 Cayley 테이블 목록은 연산자를 열거하기위한 훌륭한 단계이지만 2D 구조이므로 3D 속성 인 연관성을 확인할 수 없습니다. 다음 단계는 비 연관 함수를 필터링하는 것입니다.

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

휴! 많은 작업이 있었지만 이제는 모든 주문 n 그룹을 열거했습니다 (또는 더 나은 작업-세트가 고정되어 있으므로 동일합니다). 다음 단계 : 동 형사상을 찾으십시오. 동 형사상은 φ (x ∗ y) = φ (x) ∗ φ (y) 가되도록 두 그룹 사이의 궤적 입니다. CJam에서 이러한 bijections를 생성하는 것은 사소한 Ne!일입니다. 어떻게 확인할 수 있습니까? 내 솔루션은 x * y에 대한 Cayley 테이블의 두 복사본에서 시작합니다 . 하나의 사본에서 φ 는 행 또는 열의 순서를 건드리지 않고 모든 요소에 적용됩니다. φ (x ∗ y)에 대한 테이블을 생성합니다 . 다른 하나에서는 요소가 그대로 남아 있지만 행과 열은 φ를 통해 매핑됩니다 . 즉, 행 / 열x 는 행 / 열 φ (x)이 됩니다. φ (x) ∗ φ (y)에 대한 테이블을 생성합니다 . 이제 우리는 두 개의 테이블을 가지고 있으므로, 그것들을 비교해야합니다. 만약 그것들이 동일하다면, 동형이 발견되었습니다.

물론, 우리는 또한 동형을 테스트하기 위해 그룹 쌍을 생성해야합니다. 그룹의 모든 2 가지 조합 이 필요합니다 . CJam에는 조합 연산자가없는 것 같습니다. 각 그룹을 가져 와서 목록에서 다음에 오는 요소와 만 결합하여 생성 할 수 있습니다. 재미있는 사실 : 2 조합의 수는 n × (n-1) / 2 이며 이는 첫 번째 n-1 자연수 의 합이기도합니다 . 이러한 숫자를 삼각 숫자라고합니다. 종이에 알고리즘을 시도하고 고정 요소 당 한 행을 시도하면 그 이유를 알 수 있습니다.

: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

위의 코드는 쌍의 첫 번째 요소 인 L [X]를 수정하고 다른 그룹과 결합합니다 (각각 Y를 호출합니다 ). 이 쌍을 동형 테스트 블록으로 전달하여 잠시 후에 보여 드리겠습니다. 블록은 값들의리스트 위로 제공 Y 되는 L [X] 에 대한 동형 Y를 . 그런 다음 L [X] 가이 목록에 추가됩니다. 목록이 왜 그런 식으로 설정되어 있는지 이해하기 전에 동형 테스트를 살펴 보겠습니다.

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

이제 [{L [0], Y1, Y2, …}, {L [1], Y1, …}, …] 과 같은 세트 목록이 있습니다. 여기서의 아이디어는 전 이적 특성에 의해 두 세트가 공통된 요소를 하나 이상 갖는 경우 두 세트의 모든 그룹이 동형이라는 것입니다. 단일 세트로 집계 될 수 있습니다. 마찬가지로 L [X]를 하여 생성 된 조합에 표시되지 않을 L [X + …] , isomorphisms 각 세트를 취합 한 후 고유 요소를 가질 것이다. 따라서 동형의 수를 얻으려면 모든 동형 그룹 집합에서 정확히 몇 개의 그룹이 한 번만 나타나는지를 계산하는 것으로 충분합니다. 이를 위해 [L [0], Y1, Y2, …, L [1], Y1, …] 처럼 보이도록 세트를 풀고 목록을 정렬하여 동일한 그룹의 클러스터를 생성하고 마지막으로 그것을 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

그게 다야 사람들.

답변

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

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.

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)