Computes all the possible Cayley Tables for groups of size N

cayley_tables.py

'''
Motivated by
https://www.youtube.com/watch?v=BwHspSCXFNM&list=PLi01XoE8jYoi3SgnnGorR_XOW3IcK-TP6&index=7
'''

__author__ = 'Tim Gianitsos'

from random import randint
import numpy as np

def cayley_tables(n):
    if not n >= 1:
        return ValueError()
    if n == 1:
        # the trivial group is the singleton identity element
        return [np.array([0], dtype=np.int8)]

    a = np.empty((n,n), dtype=np.int8)
    a.fill(-1)
    # The first row and column correspond to application of the identity element
    a[0] = np.arange(n)
    a[:,0] = np.arange(n)
    res = [] # stores all possible Cayley Tables

    def fill_grid(r,c):
        '''Recursive function to create all possible Cayley tables'''
        if c == n:
            fill_grid(r + 1, 1)
            return
        if r == n:
            res.append(a.copy())
            return
        assert a[r,c] == -1

        # Try placing every allowable element in the current slot
        used_elements = set(a[r]) | set(a[:,c])
        for i in range(n):
            if i not in used_elements:
                a[r,c] = i
                fill_grid(r, c + 1)
                a[r,c] = -1

    fill_grid(1,1) # Start at (1,1) and fill table
    return res

def main():
    for i in range(1,7):
        tbls = cayley_tables(i)
        delimeter = f'\n{(i*2+3)*"-"}\n'
        newline = '\n'
        def is_abelian(e):
            return np.allclose(e, e.T) # if Cayley table is symmetric, then group is abelian
        abel_labels = [is_abelian(e) for e in tbls]
        # Interesting fact: The number of Cayley tables is greater than or equal to the number of possible groups. That is, there are some Cayley tables that encode the same group
        # For example, there are 4 possible Cayley tables of size 4, but 3 of them are effectively identical to each other, so there are only really 2 groups. That is, you can swap some of the numbers in one table to convert into another table, and all of the relationships are preserved.
        print(f'There are {len(tbls)} Cayley Table(s) of size {i} (of which {sum(abel_labels)} is/are abelian):\n{delimeter.join([(f"(ABELIAN){newline}" if a else "") + str(e) for e, a in zip(tbls, abel_labels)])}')

if __name__ == '__main__':
    main()