Jeśli nie jesteś zaznajomiony z teorią warkocza, polecam przeczytać ją najpierw. To pytanie zakłada, że znasz przynajmniej znane pojęcia i zakłada się, że dobrze znasz teorię grup
Zdefiniujmy σ n jako warkocz, w którym n- ta nić (jeden indeksowany) od góry przecina n + 1 nić, a σ n - odwrotność σ n (To jest n + 1- ty nić przecina n- ta nić).
Grupa oplot B n jest następnie wytwarzany przez <Ď 1 , σ 2 , σ 3 ,. . . , σ n-1 > . Zatem każdy warkocz na B n można zapisać jako iloczyn warkoczy σ. 1
Ustalenie, czy dwa warkocze w grupie są równe, nie jest prostym zadaniem. Może być całkiem oczywiste, że σ 1 σ 3 = σ 3 σ 1 , ale jest nieco mniej oczywiste, że na przykład σ 2 σ 1 σ 2 = σ 1 σ 2 σ 1 . 2)
Pytanie brzmi: „Jak możemy ustalić, czy dwa warkocze są takie same?”. Cóż, dwa powyższe przykłady stanowią po części. Zasadniczo następujące relacje, zwane relacjami Artina, są prawdziwe:
σ i σ j = σ j σ i ; i - j> 1
σ i σ i + 1 σ i = σ i + 1 σ i σ i + 1
Możemy wykorzystać te dwie relacje w połączeniu z aksjomatami grupy, aby udowodnić, że równe warkocze są równe. Zatem dwa warkocze są równe w przypadku wielokrotnego zastosowania tych relacji i aksjomaty grupowe mogą to wykazać.
Zadanie
Napisz program lub funkcję, aby wziąć dwa warkocze i określić, czy są one równe. Opcjonalnie możesz również przyjąć dodatnią liczbę całkowitą reprezentującą kolejność grupy.
To jest pytanie w golfa kodu, więc odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów będzie lepszych.
Wejście i wyjście
Powinieneś reprezentować plecionkę jako uporządkowaną listę generatorów (lub dowolną równoważną strukturę, np. Wektor). Możesz reprezentować generatory w dowolnej rozsądnej formie (np. Liczba całkowita, krotka dodatnia liczba całkowita i wartość logiczna).
Na równi ze standardowymi regułami problemu z deskryptorem powinieneś wypisać jedną z dwóch odrębnych wartości, a mianowicie zaakceptować odrzucenie.
Przypadki testowe
[], [] -> True
[1,-1], [] -> True
[1,2,1], [2,1,2] -> True
[1,3], [3,1] -> True
[1,3,2,1],[3,2,1,2] -> True
[1,4,-4,3,2,1], [3,2,1,2] -> True
[2,2,1], [2,1,2] -> False
[1,2,-1], [-1,2,1] -> False
[1,1,1,2],[1,1,2] -> False
1. Należy zauważyć, że gdy B n spełnia wszystkie właściwości grupy operacji na naszej grupie oplot nie przemienne, a tym samym nie jest nasza grupa abelowa.
2: Jeśli chcesz to sprawdzić sam, proponuję zastosować σ 1 - po obu stronach, jeśli narysujesz je na papierze lub zamodelujesz za pomocą rzeczywistych łańcuchów, powinno stać się jasne, dlaczego tak jest.
źródło
[],[]
[1, 4, -4, 3, 2, 1], [3, 2, 1, 2] => TRUE
Odpowiedzi:
Haskell , 190 bajtów
Wypróbuj online!
Jak to działa
Niech F n będzie wolną grupą na n generatorach x 1 ,…, x n . Jednym z pierwszych wyników teorii oplotu (Emil Artin, Theorie der Zöpfe , 1925) jest to, że mamy iniekcyjny homomorfizm f : B n → Aut ( F n ), w którym działanie f σ i z σ i jest zdefiniowane przez
f σ i ( x i ) = x i x i + 1 x i −1 ,
f σ i ( x i + 1 ) = x i ,
f σ i ( x j ) = x j dla j ∉ { i , i + 1}.
Odwrotność f σ i −1 jest określona przez
f σ i −1 ( x i ) = x i + 1 ,
f σ i −1 ( x i + 1 ) = x i + 1 −1 x i x i + 1 ,
f σ i −1 ( x j ) = x j dla j ∉ { i , i + 1}
i oczywiście Skład ten jest podany f AB = F ∘ f b .
Aby sprawdzić, czy a = b ∈ B n , wystarczy sprawdzić, że f a ( x i ) = f b ( x i ) dla wszystkich i = 1,…, n . Jest to o wiele prostszy problem w F n , gdzie musimy tylko wiedzieć, jak anulować x i za pomocą x i −1 .
W kodzie:
i!j
oblicza f σ i ( x j ) (gdzie alboi
alboj
może być ujemne, reprezentujące odwrotność),foldr(%)[]
dokonuje redukcji w grupie wolnej,i&a
oblicza f a ( x i ),a?n
oblicza [ f a ( x 1 ),…, f a ( x n )],(a#b)n
jest test równość a = b, w B n .źródło
Python 2 ,
270263260250249241 bajtówWypróbuj online!
Implementacja metody „odwracania podsłów” w celu rozwiązania problemu izotopii plecionki: a = b iff ab ^ -1 = tożsamość.
Algorytm zaczerpnięty z: Skuteczne rozwiązania problemu izotopii oplotu, Patrick Dehornoy ; opisuje kilka innych algorytmów, które mogą być interesujące ...
Algorytm działa poprzez marsz od lewej do prawej na liście, szukając liczby ujemnej, a następnie liczby dodatniej; tj. pod-słowo w postaci x i -1 x j z i, j> 0.
Wykorzystuje następujące równoważniki:
x i -1 x j = x j x i x j -1 x i -1, jeśli i = j + 1 lub j = i + 1
x i -1 x j = tożsamość (pusta lista), jeśli i == j
x i -1 x j = x j x i -1 w przeciwnym razie.
Po wielokrotnym zastosowaniu otrzymujemy listę postaci
w1 + w2
, w której każdy elementw1
jest dodatni, a każdy elementw2
jest ujemny. (To jest działanie funkcjig
).Następnie ponownie stosujemy
g
listęw2 + w1
; wynikowa lista powinna być pusta, jeśli oryginalna lista była równoważna z tożsamością.źródło