Czy te warkocze są równe?

13

Jeśli nie jesteś zaznajomiony z teorią warkocza, polecam przeczytać 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 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 z 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.

Ad Hoc Garf Hunter
źródło
Nie jestem zaznajomiony z teorią warkocza, dlatego jestem VTCing jako totalny bełkot (tylko żartuję)
Cairney Coinheringaahing
2
Czy możemy prosić o kilka przypadków testowych?
HyperNeutrino,
@HyperNeutrino Przepraszamy, zapomniałem je dodać. Dodano teraz Możesz zaproponować więcej.
Ad Hoc Garf Hunter,
@ Sugestia przypadku testowegoWheatWizard:[],[]
Pavel
Proponowany przypadek testowy:[1, 4, -4, 3, 2, 1], [3, 2, 1, 2] => TRUE
HyperNeutrino,

Odpowiedzi:

11

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 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 nAut ( 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 = Ff b .

Aby sprawdzić, czy a = bB 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!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 1 ),…, f a ( x n )],
  • i (a#b)njest test równość a = b, w B n .
Anders Kaseorg
źródło
4

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ą.

Chas Brown
źródło