Цикл - это довольно простая алгебраическая структура. Это кортеж (G +) , где G представляет собой множество , а + является бинарным оператором G × G → G . То есть + берет два элемента из G и возвращает новый элемент. Оператору также необходимо выполнить два свойства

• Отмена: Для каждого a и b в G существуют уникальные x и y в G, такие что

  a + x = b
  y + a = b
  

• Идентичность: в G есть такое e , что для каждого a в G

  e + a = a
  a + e = a
  

Если вы знакомы с концепцией группы, вы можете заметить, что цикл - это просто группа, которая не имеет ассоциативного свойства.

Циклы довольно просты, поэтому людям нравится добавлять больше правил, чтобы сделать новые структуры более интересными. Одной из таких структур является петля Муфанга, которая также удовлетворяет следующим четырем тождествам для x , y и z в G

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

Например, следующая таблица Кэли представляет цикл Муфанга:

0  1  2  3
1  0  3  2
2  3  0  1
3  2  1  0

(Если вы не знакомы, таблица Кэли - это квадратная матрица M, где M _{i, j} равно i + j . Это удобный способ представления бинарных операторов на множестве.)

Мы можем доказать, что идентичность существует довольно легко 0. Отмена немного сложнее показать, но подход грубой силы дает эту таблицу

b a → 0 1 2 3
↓
0     0 1 2 3
1     1 0 3 2
2     2 3 0 1
3     3 2 1 0

Где наши элементы являются решениями для

a + x = b = x + a

(Вы можете заметить, что эта таблица идентична нашей таблице Кейли. Я оставлю это в качестве упражнения для читателя, чтобы выяснить, почему это так для этой петли Муфанга)

Теперь нам нужно проверить тождества Муфанга для нашей структуры. Есть два способа сделать это для конкретной структуры. Первый способ - понять, что она ассоциативна и, таким образом, автоматически удовлетворяет критериям, однако в общем случае это не сработает, поэтому мы бы предпочли грубый результат. Здесь есть 3 свободные переменные с потенциалом 4 значения в каждом выражении. Это означает, что мы должны выполнить 7 * 4 ³ или 448 вычислений. Я опущу необработанные вычисления, но вот несколько Haskell, которые вы можете использовать, чтобы проверить это .

задача

Учитывая положительное целое число n в качестве входных данных, количество циклов Муфанга, которые имеют порядок n . (порядок группы равен размеру набора)

Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньшее количество байтов будет лучше.

Контрольные примеры

Вот количество циклов Муфанга для первых 71 входа

1,1,1,2,1,2,1,5,2,2,1,6,1,2,1,19,1,5,1,6,2,2,1,20,2,2,5,5,1,4,1,122,1,2,1,18,1,2,2,19,1,7,1,5,2,2,1,103,2,5,1,6,1,17,2,17,2,2,1,18,1,2,4,4529,1,4,1,6,1,4,1

Python 3 , 475 410 байт

Спасибо Mr.Xcoder за сохранение некоторых байтов!

Используйте симметрию формулы, чтобы сохранить 65 байтов. Да, это много.

from itertools import*
n=int(input())
P=permutations
R=[*range(n)]
u=[]
A=all
S=sorted
for T in P(P(R),n):u+=[T]*(A(A(R==S(x)for x in
t)and any([*x]==S(x)for x in t)and
A(t[z][t[x][t[z][y]]]==t[t[t[z][x]][z]][y]and
t[t[z][x]][t[y][z]]==t[t[z][t[x][y]]][z]for x in R
for y in R for z in R)for t
in(T,[*zip(*T)]))and A(A(1-A(p[T[i][j]]==U[p[i]][p[j]]for i in R
for j in R)for p in P(R))for U in u))
print(len(u))

Попробуйте онлайн!

Некоторые из них andмогут быть заменены *, что приводит к снижению количества пользователей, но за счет значительно более медленного времени выполнения:

Python 3 , ??? байтов

[TODO поставить код здесь]

(конечно, не все *делает программу значительно медленнее, только некоторые из них являются критическими)

Ungolfed:

from itertools import *
n = 4 # int(input())
rangeN = list(range(n))

def is_moufang_loop(T):
    A = tuple(zip(*T))
    return all(
        all(sorted(x) == rangeN for x in t)
        and any(list(x) == sorted(x) for x in t)
        and all(
                T[z][T[x][T[z][y]]] == T[T[T[z][x]][z]][y]
            and T[T[z][x]][T[y][z]] == T[T[z][T[x][y]]][z]
            for x in rangeN for y in rangeN for z in rangeN)
        for t in (T, A)
    )

def isomorphic(loop1, loop2):
    for p in permutations(rangeN):
        if all(
            p[loop1[i][j]] == loop2[p[i]][p[j]]
            for i in rangeN
            for j in rangeN
        ): return True
    return False

unique_moufang_loops = []
for x in [
        cayley_table 
        for cayley_table in permutations(permutations(rangeN), n)
        if is_moufang_loop(cayley_table)
]:
    if all(not isomorphic(x, y) for y in unique_moufang_loops):
        unique_moufang_loops.append(x)

print(len(unique_moufang_loops))

Попробуйте онлайн!

_{Нет полос прокрутки ...}

Объяснение:

Программа довольно проста.

• Каждый возможный «бинарный оператор» представлен таблицей Кэли (индексирование 0).
• Свойство «идентичность» подразумевает, что существует eтакое, что и e'-ая строка, и e' -й столбец равны [0, 1, 2, ..., n-1], что является тем же условием, что и

  и массив, Tи его транспонирование имеют строку, равную [0, 1, 2, ..., n-1].

• Свойство "отмены" эквивалентно

  Каждая строка и каждый столбец являются перестановкой [0, 1, 2, ..., n-1].

Итак, часть

all(
        all(sorted(x) == rangeN for x in t) 
        and any(list(x) == sorted(x) for x in t) 
        for t in (T, A))

кода проверяет это. (для всей строки в массиве Tи его транспонирования Aсортировка равна rangeN, и существует строка в обоих, Tи Aэто равно самой сортировке)

Четыре условия петли Муфанга проверяются вручную.

z + (x + (z + y)) = ((z + x) + z) + y
((y + z) + x) + z = y + (z + (x + z))
(z + x) + (y + z) = (z + (x + y)) + z
(z + x) + (y + z) = z + ((x + y) + z)

В коде (a + b)представлен как T[a][b]. (из-за представления в виде таблицы Кэли). Используйте сравнение равенства цепочек Python, чтобы избежать дублирования (z + x) + (y + z).

Однако, поскольку формула симметрична:

Если мы переключим операнды +в первой формуле, мы получим вторую формулу; и если мы поменяем операнды +в третьей формуле, мы получим четвертую формулу с xи yпоменялись местами.

Обратите внимание, что транспонирование таблицы Кэли эквивалентно бинарным операторам, чьи операнды поменялись местами. ( x + y -> y + x)

Наконец, все кандидаты в таблицу Cayley выбираются из

permutations(permutations(rangeN), n) 

так что каждая строка является перестановкой rangeN(которая есть [0, 1, 2, ..., n-1]) и есть nотдельные строки.