Factorisation d'une permutation

**SpiceGuid** · 25/04/2009, 18h36

Je cherche un algo de factorisation d'une permutation.

Je note :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(2 5 7 11 3 ....)

La permutation qui met le 2ième élément à la place du 1ier, le 5ième à la place du 2nd, le 7ième à la place du 3ième, le 11ième à la place du 4ième, etc...

Je voudrais un algo pour factoriser (si c'est possible) en une suite de triangulations (permutation circulaire de trois éléments) du genre (5 3 2)(8 4 1)(6 9 3)...

edit:
(a b c) a pour effet que b prend la place de c, a prend la place de b et c prend la place de a.

**Zavonen** · 25/04/2009, 23h29

A mon avis ce n'est pas possible (du moins si les cycles opèrent sur des triplets disjoints, comme dans ton exemple).
Explication: l'ordre d'une permutation circulaire sur 3 éléments est 3. Si c'était possible cela voudrait dire que toute permutation de n entiers a, en tant qu'élément du groupe symétrique Sn, un ordre 3, ce qui est évidemment faux.
Pour ce qui est de décomposer une permutation en cycles, je donne un exemple dans mon cours Bases-->applications-->cycles.

**SpiceGuid** · 26/04/2009, 17h41

Merci. Ma question manquait de précision.

les triplets sont quelconques (pas disjoints, dans mon exemple l'élément 3 est présent dans 2 triangulations différentes)
l'application à laquelle je pense ce sont des puzzles de type Rubiks Cube où le nombre d'éléments concernés est un multiple de 3 (vu qu'un cube possède 12 arrêtes)

J'ai suivi le lien vers le déjà fameux cours de math et c'est encourageant de voir que le raisonnement par récurrence est toujours aussi 'constructif'.
Du coup avec un peu de soin et d'application je devrais pourvoir m'en sortir tout seul.

**Zavonen** · 26/04/2009, 18h27

On y est presque !
Tu commences par décomposer en cycles.
Ensuite tu décomposes chaque cycle en produit de transpositions de deux entiers consécutifs. C'est fait dans mon cours ...
Après tu remarques la chose suivante:
Si tu composes deux transpositions sur des entiers consécutifs ayant un élément commun, tu obtiens un cycle d'ordre 3 exemple (2,1) et (3,2), la composition donne (3,1,2).
Un algo possible:
Suppose que dans la décomposition de s il y ait un cycle d'ordre au moins égal à trois. Décompose ce cycle en produit de transpositions d'éléments consécutifs. Prend le produit de ces deux premières transpos qui est un cyle d'ordre 3 disons c, et essaie d'appliquer la récurence à c^-1 s, qui opère sur n-3 éléments. Ta récurrence s'arrête quand dans la décomposition tu ne peux plus trouver un cycle d'ordre au moins égal à 3. Cela veut dire que s est alors l'identité ou un produit de transpositions opérant sur des paires disjointes. Il suffit maintenant d'étudier ce cas. Une transposition peut elle être écrite comme produit de plusieurs cycles d'ordre 3 non disjoints ? A toi de voir