Jika Anda tidak terbiasa dengan Braid-Theory, saya sarankan Anda membaca ini dulu. Pertanyaan ini mengasumsikan bahwa Anda paling tidak terbiasa dengan konsep-konsep yang ada dan menganggap Anda sudah terbiasa dengan teori-kelompok

Mari kita definisikan σ _n menjadi jalinan di mana untai ke- n (Satu diindeks) dari atas menyilang ke untai ke- 1 , dan σ _n ^- menjadi kebalikan dari σ _n (Itulah ke- n ke- 1) strand melintasi strand ke- n ).

Grup kepang B _n kemudian dihasilkan oleh <σ ₁ , σ ₂ , σ ₃ ,. . . , σ _n-1 > . Dengan demikian setiap kepang pada B _n dapat ditulis sebagai produk kepang σ. ¹

Menentukan apakah dua kepang pada suatu kelompok sama bukanlah tugas yang mudah. Mungkin cukup jelas bahwa σ ₁ σ ₃ = σ ₃ σ ₁ , tetapi agak kurang jelas bahwa misalnya σ ₂ σ ₁ σ ₂ = σ ₁ σ ₂ σ ₁ . ²

Jadi pertanyaannya adalah "Bagaimana kita bisa menentukan apakah dua kepang sama?". Nah dua contoh di atas masing-masing mewakili sedikit dari ini. Secara umum hubungan berikut, yang disebut hubungan Artin, adalah benar:

• σ _i σ _j = σ _j σ _i ; i - j> 1

• σ _i σ _{i + 1} σ _i = σ _{i + 1} σ _i σ _{i + 1}

Kita dapat menggunakan dua hubungan ini bersamaan dengan aksioma kelompok untuk membuktikan bahwa setiap kepang yang sama adalah sama. Jadi, dua kepang sama jika aplikasi berulang hubungan ini dan aksioma kelompok dapat menunjukkan demikian.

Tugas

Anda akan menulis sebuah program atau fungsi untuk mengambil dua kepang dan menentukan apakah keduanya sama atau tidak. Anda juga dapat memilih bilangan bulat positif yang mewakili urutan grup.

Ini adalah pertanyaan kode-golf sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.

Masukan dan keluaran

Anda harus mewakili Braid sebagai daftar generator yang dipesan, (atau struktur apa pun yang setara, misalnya vektor). Anda dapat mewakili generator dalam bentuk apa pun yang wajar (misalnya bilangan bulat, dua tupel bilangan bulat positif dan boolean).

Setara dengan aturan masalah keputusan standar Anda harus menampilkan salah satu dari dua nilai yang berbeda, yang menerima penolakan.

Uji Kasus

[],       []              -> 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: Perhatikan bahwa meskipun B _n memenuhi semua properti grup, operasi pada grup braid kami tidak komutatif, dan dengan demikian grup kami tidak abelian.}

^{2: Jika Anda ingin memverifikasi ini untuk Anda sendiri, saya sarankan menerapkan σ ₁ - untuk kedua sisi, Jika Anda menggambar keduanya di atas kertas, atau memodelkannya dengan string yang sebenarnya, itu akan menjadi jelas mengapa hal ini terjadi.}

Haskell , 190 byte

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

Cobalah online!

Bagaimana itu bekerja

Biarkan F _n menjadi grup gratis di n generator x ₁ ,…, x _n . Salah satu hasil pertama dalam teori jalinan (Emil Artin, Theorie der Zöpfe , 1925) adalah bahwa kita memiliki homomorfisme suntik f : B _n → Aut ( F _n ) di mana aksi f _{σ i} dari σ _i didefinisikan oleh

f _{σ i} ( x _i ) = x _i x _{i + 1} x _i ⁻¹ ,
f _{σ i} ( x _{i + 1} ) = x _i ,
f _{σ i} ( x _j ) = x _j untuk j ∉ { i , i + 1}.

Invers f _{σ i ⁻¹} diberikan oleh

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 untuk j ∉ { i , i + 1}

dan tentu saja komposisi diberikan oleh f _ab = f _a ∘ f _b .

Untuk menguji apakah a = b ∈ B _n , cukup untuk menguji bahwa f _a ( x _i ) = f _b ( x _i ) untuk semua i = 1,…, n . Ini adalah masalah yang lebih sederhana di F _n , di mana kita hanya perlu tahu cara membatalkan x _i dengan x _i ⁻¹ .

Dalam kode:

• i!jmenghitung f _{σ i} ( x _j ) (di mana salah satu iatau jmungkin negatif, mewakili inversi),
• foldr(%)[] melakukan pengurangan dalam grup gratis,
• i&amenghitung f _a ( x _i ),
• a?nmenghitung [ f _a ( x ₁ ), ..., f _a ( x _n )],
• dan (a#b)nmerupakan uji persamaan untuk a = b dalam B _n .

Python 2 , 270 263 260 250 249 241 byte

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)==[]

Cobalah online!

Implementasi metode 'subword reversing' untuk memecahkan masalah kepang isotop: a = b iff ab ^ -1 = identitas.

Algoritma diambil dari: Solusi efisien untuk masalah isotop kepang, Patrick Dehornoy ; ia menjelaskan beberapa algoritma lain yang mungkin menarik ...

Algoritma ini bekerja dengan berbaris kiri ke kanan dalam daftar, mencari angka negatif diikuti oleh angka positif; yaitu, sub-kata dari bentuk x _i ^-1 x _j dengan i, j> 0.

Ini menggunakan kesetaraan berikut:

x _i ^-1 x _j = x _j x _i x _j ^-1 x _i ^-1 jika i = j + 1 atau j = i + 1

x _i ^-1 x _j = identitas (daftar kosong) jika saya == j

x _i ^-1 x _j = x _j x _i ^-1 jika tidak.

Dengan aplikasi berulang, kita berakhir dengan daftar formulir w1 + w2, di mana setiap elemen w1positif dan setiap elemen w2negatif. (Ini adalah aksi dari fungsi g).

Kami kemudian menerapkan gkedua kalinya pada daftar w2 + w1; daftar yang dihasilkan harus kosong jika daftar aslinya setara dengan identitas.