Si vous n'êtes pas familier avec la théorie de la tresse, je vous recommande de lire ceci en premier. Cette question suppose que vous êtes au moins familier avec les concepts en jeu et suppose que vous connaissez bien la théorie des groupes

Définissons σ _n comme la tresse dans laquelle le n ème brin (un indexé) du haut croise le n + 1 ème brin, et σ _n ^- comme l'inverse de σ _n (c'est-à-dire le n + 1 ème brin croise le n e brin).

Le groupe de tresses B _n est alors généré par <σ ₁ , σ ₂ , σ ₃ ,. . . , σ _n-1 > . Ainsi, chaque tresse sur B _n peut être écrite comme le produit des σ-tresses. ¹

Déterminer si deux tresses sur un groupe sont égales n'est pas une tâche simple. Il peut être assez évident que σ ₁ σ ₃ = σ ₃ σ ₁ , mais il est un peu moins évident que par exemple σ ₂ σ ₁ σ ₂ = σ ₁ σ ₂ σ ₁ . ²

La question est donc "Comment déterminer si deux tresses sont identiques?". Eh bien, les deux exemples ci-dessus représentent chacun un peu de cela. En général, les relations suivantes, appelées relations d'Artin, sont vraies:

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

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

Nous pouvons utiliser ces deux relations conjointement avec les axiomes du groupe pour prouver que toutes les tresses égales sont égales. Ainsi, deux tresses sont égales si l'application répétée de ces relations et les axiomes de groupe peuvent le démontrer.

Tâche

Vous allez écrire un programme ou une fonction pour prendre deux tresses et déterminer si elles sont égales ou non. Vous pouvez également éventuellement prendre un entier positif représentant l'ordre du groupe.

Il s'agit d'une question de code-golf donc les réponses seront notées en octets, avec moins d'octets étant mieux.

Entrée et sortie

Vous devez représenter une tresse comme une liste ordonnée de générateurs (ou toute structure équivalente, par exemple un vecteur). Vous pouvez représenter les générateurs sous toute forme raisonnable (par exemple, un entier, deux tuple d'un entier positif et un booléen).

À égalité avec les règles de problème de descente standard, vous devez sortir l'une des deux valeurs distinctes, un accepter un rejet.

Cas de test

[],       []              -> 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: Notez que si B _n satisfait toutes les propriétés d'un groupe, l'opération sur notre groupe de tresses n'est pas commutative, et donc notre groupe n'est pas abélien.}

^{2: Si vous souhaitez vérifier par vous-même, je suggère d'appliquer σ ₁ - des deux côtés.Si vous dessinez les deux sur du papier ou les modélisez avec des chaînes réelles, il devrait devenir évident pourquoi c'est le cas.}

Haskell , 190 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Soit F _n le groupe libre sur n générateurs x ₁ ,…, x _n . L'un des premiers résultats de la théorie des tresses (Emil Artin, Theorie der Zöpfe , 1925) est que nous avons un homomorphisme injectif f : B _n → Aut ( F _n ) où l' action f _{σ i} de σ _i est définie par

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

L'inverse f _{σ i ⁻¹} est donné par

f _{σ i ⁻¹} ( x _i ) = x _{i + 1} ,
f _{σ i ⁻¹} ( x _{i + 1} ) = x _{i + 1} ^-1 x _i x _{i + 1} ,
f _{σ i ⁻¹} ( x _j ) = x _j pour j ∉ { i , i + 1}

et bien sûr la composition est donnée par f _ab = f _a ∘ f _b .

Pour tester si a = b ∈ B _n , il suffit de tester que f _a ( x _i ) = f _b ( x _i ) pour tout i = 1,…, n . C'est un problème beaucoup plus simple dans F _n , où il suffit de savoir comment annuler x _i avec x _i ⁻¹ .

Dans le code:

• i!jcalcule f _{σ i} ( x _j ) (où soit iou jpeut être négatif, représentant un inverse),
• foldr(%)[] effectue une réduction dans le groupe libre,
• i&acalcule f _a ( x _i ),
• a?ncalcule [ f _a ( x ₁ ),…, f _a ( x _n )],
• et (a#b)nest le test d'égalité pour a = b dans B _n .

Python 2 , 270 263 260 250 249 241 octets

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

Essayez-le en ligne!

Implémentation de la méthode de «renversement de sous-mots» pour résoudre le problème d'isotopie des tresses: a = b ssi ab ^ -1 = l'identité

Algorithme tiré de: Solutions efficaces au problème d'isotopie des tresses, Patrick Dehornoy ; il décrit plusieurs autres algorithmes qui peuvent être intéressants ...

Cet algorithme fonctionne en marchant de gauche à droite dans la liste, en recherchant un nombre négatif suivi d'un nombre positif; c'est-à-dire, un sous-mot de la forme x _i ^-1 x _j avec i, j> 0.

Il utilise les équivalences suivantes:

x _i ^-1 x _j = x _j x _i x _j ^-1 x _i ^-1 si i = j + 1 ou j = i + 1

x _i ^-1 x _j = identité (liste vide) si i == j

x _i ^-1 x _j = x _j x _i ^-1 sinon.

Par application répétée, nous nous retrouvons avec une liste de la forme w1 + w2, où chaque élément de w1est positif et chaque élément de w2est négatif. (C'est l'action de la fonction g).

Nous appliquons ensuite gune deuxième fois à la liste w2 + w1; la liste résultante doit être vide si la liste d'origine était équivalente à l'identité.