Pętla jest dość prostą strukturą algebraiczną. Jest krotką (G +), w którym G jest zbiorem a + jest operatorem, G xg → G . To znaczy + pobiera dwa elementy z G i zwraca nowy element. Operator jest również zobowiązany do spełnienia dwóch właściwości

• Rezygnacja: Dla każdego A i B w G istnieje unikalny X i Y w G , tak że

  a + x = b
  y + a = b
  

• Tożsamość: Istnieje e w G takie, że dla każdego a w G

  e + a = a
  a + e = a
  

Jeśli znasz pojęcie grupy, możesz zauważyć, że pętla jest tylko grupą, która nie ma właściwości asocjacyjnej.

Pętle są dość proste, więc ludzie lubią dodawać więcej reguł, aby nowe struktury były bardziej interesujące. Jedna taka struktura jest pętla Moufang który jest pętla także spełnia następujące cztery Tożsamości Forall x , y i z, w 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)

Na przykład poniższa tabela Cayley przedstawia pętlę Moufanga:

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

(Jeśli nie jesteś zaznajomiony, tabela Cayleya jest macierzą kwadratową M, gdzie M _{i, j} jest równa i + j . Jest to przydatny sposób reprezentowania operatorów binarnych na zbiorze.)

Możemy pokazać, że tożsamość jest dość łatwa 0. Anulowanie jest nieco trudniejsze do pokazania, ale podejście oparte na brutalnej sile daje tę tabelę

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

Gdzie nasze elementy są rozwiązaniami

a + x = b = x + a

(Możesz zauważyć, że ten stół jest identyczny z naszym stołem Cayley. Zostawię to jako ćwiczenie dla czytelnika, aby dowiedzieć się, dlaczego tak jest w przypadku tej pętli Moufang)

Teraz musimy zweryfikować tożsamość Moufang dla naszej struktury. Istnieją dwa sposoby, aby to zrobić dla konkretnej struktury. Pierwszym sposobem jest uświadomienie sobie, że jest ona asocjacyjna, a zatem automatycznie spełnia kryteria, jednak nie będzie to ogólnie działać, więc wolelibyśmy brutalną siłę wyniku. Istnieją tutaj 3 wolne zmienne, z których każda może zawierać 4 wartości w każdym wyrażeniu. Oznacza to, że musimy wykonać obliczenia 7 * 4 ³ lub 448. Pominę surowe obliczenia, ale oto Haskell, którego możesz użyć, aby to sprawdzić .

Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą n jako wynik wyjściowy, liczbę pętli Moufanga, które mają porządek n . (kolejność grupy to rozmiar zestawu)

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

Oto liczba pętli Moufanga dla pierwszych 71 wejść

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 bajtów

Dzięki Mr.Xcoder za uratowanie niektórych bajtów!

Użyj symetrii formuły, aby zapisać 65 bajtów. Tak, to dużo.

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))

Wypróbuj online!

Niektóre andmogą zostać zastąpione przez *, co powoduje zmniejszenie liczby bajtów, ale kosztem znacznie wolniejszego czasu realizacji:

Python 3 , ??? bajty

[TODO umieść tutaj kod]

(oczywiście nie wszystkie *sprawiają, że program jest znacznie wolniejszy, tylko niektóre z nich są krytyczne)

Nie golfowany:

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))

Wypróbuj online!

_{Brak pasków przewijania ...}

Wyjaśnienie:

Program jest dość prosty.

• Każdy możliwy „operator binarny” jest reprezentowany przez tabelę Cayleya (indeksowanie 0).
• Właściwość „tożsamość” implikuje, że istnieją etakie, że zarówno e„wiersz, jak i e„ kolumna są równe [0, 1, 2, ..., n-1], co jest takim samym warunkiem jak

  zarówno tablica, jak Ti jej transpozycja mają wiersz równy [0, 1, 2, ..., n-1].

• Właściwość „anulowanie” jest równoważna z

  Każdy wiersz i każda kolumna to permutacja [0, 1, 2, ..., n-1].

Więc część

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

kodu sprawdza to. (dla wszystkich wierszy w tablicy Ti jej transpozycji Asortowanie jest równe rangeNi istnieje wiersz w obu TiA równa na siebie sortowane)

Cztery warunki pętli Moufang są sprawdzane ręcznie.

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)

W kodzie (a + b)jest reprezentowany jako T[a][b]. (z powodu przedstawienia jako tabela Cayley). Użyj porównania równości łańcuchów w Pythonie, aby uniknąć powielania (z + x) + (y + z).

Ponieważ jednak formuła jest symetryczna:

Jeśli zmienimy operandy +w pierwszej formule, otrzymamy drugą formułę; a jeśli zmienimy operandy +w trzeciej formule, otrzymamy czwartą formułę z xi yzamieniłem miejsce.

Zauważ, że transpozycja tabeli Cayleya jest równoważna operatorom binarnym, które zamieniły operandy. (x + y -> y + x )

Na koniec wybierani są wszyscy kandydaci do stołu Cayley

permutations(permutations(rangeN), n) 

tak że każdy wiersz jest permutacją rangeN(która jest [0, 1, 2, ..., n-1]) i istnieją nosobne wiersze.