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 <Ď ₁ , σ ₂ , σ ₃ ,. . . , σ _n-1 > . Zatem każdy warkocz na B _n można zapisać jako iloczyn warkoczy σ. ¹

Ustalenie, czy dwa warkocze w grupie są równe, nie jest prostym zadaniem. Może być całkiem oczywiste, że σ ₁ σ ₃ = σ ₃ σ ₁ , ale jest nieco mniej oczywiste, że na przykład σ ₂ σ ₁ σ ₂ = σ ₁ σ ₂ σ ₁ . ²⁾

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ć σ ₁ - po obu stronach, jeśli narysujesz je na papierze lub zamodelujesz za pomocą rzeczywistych łańcuchów, powinno stać się jasne, dlaczego tak jest.}

Haskell , 190 bajtów

i!j|j<0=reverse$map(0-)$i!(-j)|i==j=[i,i+1,-i]|i+1==j=[i]|i+j==0=[j+1]|i+j==1=[-j,-i,j]
_!j=[j]
j%(k:a)|j+k==0=a
j%a=j:a
i&a=foldr(%)[]$foldr((=<<).(!))[i]a
a?n=map(&a)[1..n]
(a#b)n=a?n==b?n

Wypróbuj online!

Jak to działa

Niech F _n będzie wolną grupą na n generatorach x ₁ ,…, 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 ⁻¹ ,
f _{σ i} ( x _{i + 1} ) = x _i ,
f _{σ i} ( x _j ) = x _j dla j ∉ { i , i + 1}.

Odwrotność f _{σ i ⁻¹} jest określona przez

f _{σ i ⁻¹} ( x _i ) = x _{i + 1} ,
f _{σ i ⁻¹} ( x _{i + 1} ) = x _{i + 1} ⁻¹ x _i x _{i + 1} ,
f _{σ i ⁻¹} ( 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 ⁻¹ .

W kodzie:

• i!joblicza f _{σ i} ( x _j ) (gdzie albo ialbo jmoże być ujemne, reprezentujące odwrotność),
• foldr(%)[] dokonuje redukcji w grupie wolnej,
• i&aoblicza f _a ( x _i ),
• a?noblicza [ f _a ( x ₁ ),…, f _a ( x _n )],
• i (a#b)njest test równość a = b, w B _n .

Python 2 , 270 263 260 250 249 241 bajtów

def g(b,i=0):
 while i<len(b)-1:
  R,s=b[i:i+2]
  if R<0<s:b[i:i+2]=[[],[s,-R,-s,R],[s,R]][min(abs(R+s),2)];i=-1
  i+=1
 return b
def f(a,b):
 b=g(a+[-v for v in b][::-1]);i=0
 while i<len(b)and b[0]>0:b=b[1:]+[b[0]];i+=1   
 return g(b)==[]

Wypró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 element w1jest dodatni, a każdy element w2jest ujemny. (To jest działanie funkcji g).

Następnie ponownie stosujemy glistę w2 + w1; wynikowa lista powinna być pusta, jeśli oryginalna lista była równoważna z tożsamością.