Counting groups of a given size
CJam, 189 187 bytes
This one's gonna be tough to explain... Time complexity is guaranteed to be 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=},,}{!!}?
If you're brave enough, try it online. On my crappy laptop I can get up to 6 with the Java interpreter or 5 in the online interpreter.
Explanation
I don't have a big math background (just finished high school, starting CS at uni next week). So bear with me if I make mistakes, state the obvious, or do things in horribly inefficent ways.
My approach is a brute force, though I tried to make it a little more clever. The main steps are:
- Generate all the possible operands ∗ for a group of order n (i.e., enumerate all groups of order n);
- Generate all the possible bijections φ between two groups of order n;
- Using the results from steps 1 and 2, determine all isomorphisms between two groups of order n;
- Using the result from step 3, count the number of groups up to isomorphism.
Before looking at the how each step is done, let's get some trivial code out of the way:
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)
The following algorithm doesn't work correctly with n < 4, the cases from 0 to 3 are handled with a double negation.
From now on, the elements of a group will be written as {1, a, b, c, ...}, where 1 is the identity element. In the CJam implementation, the corresponding elements are {0, 1, 2, 3, ...}, where 0 is the identity element.
Let's start from step 1. Writing all possible operators for a group of order n is equivalent to generating all the valid n×n Cayley tables. The first row and column are trivial: they are both {1, a, b, c, ...} (left-to-right, up-to-down).
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
Knowing that a Cayley table is also a reduced Latin square (due to the cancellation property) allows to generate the possible tables row-by-row. Starting from the second row (index 1), we generate all the unique permutations for that row, keeping the first column fixed to the value of the index.
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
Not all those permutations are valid, of course: each row and column must contain all the elements exactly one time. A filter block is used for this purpose (a truthy value keeps the permutation, a falsy one removes it):
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
Note that I am filtering inside the generation loop: this makes the code a bit longer (compared to distinct generation and filtering), but greatly improves performance. The number of permutations of a set of size n is n!, so the shorter solution would require a lot of memory and time.
A list of valid Cayley tables is a great step towards enumerating the operators, but being a 2D structure, it can't check for associativity, which is a 3D property. So next step is filtering out non-associative functions.
{ }, 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]
Phew! Lots of work, but now we have enumerated all groups of order n (or better, the operations on it - but the set is fixed, so it's the same thing). Next step: find isomorphisms. An isomorphism is a bijection between two of those groups such that φ(x ∗ y) = φ(x) ∗ φ(y). Generating those bijections in CJam is trivial: Ne! will do it. How can we check them? My solution starts from two copies of the Cayley table for x ∗ y. On one copy, φ is applied to all elements, without touching the order of rows or columns. This generates the table for φ(x ∗ y). On the other one the elements are left as they are, but rows and columns are mapped through φ. That is, the row/column x becomes the row/column φ(x). This generates the table for φ(x) ∗ φ(y). Now that we have the two tables, we just have to compare them: if they are the same, we have found an isomorphism.
Of course, we also need to generate the pairs of groups to test isomorphism on. We need all the 2-combinations of the groups. Looks like CJam has no operator for combinations. We can generate them by taking each group and combining it only with the elements following it in the list. Fun fact: the number of 2-combinations is n × (n - 1) / 2, which is also the sum of the first n - 1 natural numbers. Such numbers are called triangular numbers: try the algorithm on paper, one row per fixed element, and you'll see why.
: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
The code above fixes the first element of the pair, L[X], and combines it with other groups (let's call each one of those Y). It passes the pair to a isomorphism test block that I'll show in a moment. The block gives back a list of values of Y for which L[X] is isomorphic to Y. Then L[X] is appended to this list. Before understanding why the lists are set up in such a way, let's look at the isomorphism test:
\_@ 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
Great, now we have a list of sets like [{L[0], Y1, Y2, ...}, {L[1], Y1, ...}, ...]. The idea here is that, by transitive property, if any two sets have at least one element in common then all the groups in the two sets are isomorphic. They can be aggregated into a single set. As L[X] will never appear in the combinations generated by L[X+...], after aggregating each set of isomorphisms will have one unique element. So, to get the number of isomorphisms, it's sufficient to count how many groups appear exactly once in all sets of isomorphic groups. To do this, I unwrap the sets so they look like [L[0], Y1, Y2, ..., L[1], Y1, ...], sort the list to create clusters of the same group and finally RLE-encode it.
:~ 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
That's all, folks.
CJam, 73 bytes
0ri:Re!Rm*{:Tz0=R,=[R,Te_]m!{~ff{T==}e_}/=&},{:T,e!{:PPff{T==P#}}%$}%Q|,+
The time complexity of the above code is worse than O(n!n).
Input n=4 is already to much for the online interpreter.
Using the Java interpreter, input n=5 could be possible, if you have enough RAM and patience.
Finding groups
Given a group (G, ∗) of order n, we can pick an arbitrary bijection φ : G -> Cn such that φ(e) = 0.
φ will become an isomorphism of (G, ∗) and (Cn, ∗') if we define ∗' by x ∗' y = φ(φ-1(x) ∗ φ-1(y)).
This means that it suffices to study all group operators in Cn such that 0 is the neutral element.
We will represent a group operator ∗ in Cn by a rectangular array T of dimensions n × n such that T[x][y] = x ∗ y.
To generate such an array, we can start by picking a permutation of Cn for each of its n rows.
This way, 0 will be present in all rows (but not necessarily all columns), meaning that the third condition (existence of an inverse) will be fulfilled, whatever e may be.
We can fix e = 0 by requiring that the first column of T is equal to Cn. In particular, the second condition (existence of a neutral element) will hold.
To verify that T corresponds to a group operator, all that's left to do is verifying that the first condition (associativity) holds. This can be done exhaustively by checking that T[T[x][y]][z] == T[x][T[y][z]] for all x, y, z in Cn.
Counting non-isomorphic groups
The above method for finding groups will yield some isomorphic groups. Rather than identifying which ones are isomorphic, we generate the family of all isomorphic groups for every one of them.
This can done achieved by iterating over all bijections φ : Cn -> Cn, and determining the associated array Tφ, defined by Tφ[x][y] = φ-1(T[φ(x)][φ(y)]).
All that's left to do is counting the number of distinct families.
What the code does
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 bytes
- Saved eight bytes thanks to 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)
Try it online!
Using the equivalence between the number of non-isomorphic subgroups of order \$n\$ of \$\ \Sigma_n\$ and the number of isomorphic equivalence classes of finite groups of order \$n\$.
Link to verbose version.