Décomposition des permutations

[invitee3a2ba33]

Salut a tous, je souhaite savoir si quelqu'un a l'algorithme de décomposition des permutations en produit de transpositions et que cette décomposition soit la plus minimale.
Merci d'avance.
-----

[invite332de63a]

Pour avoir la plus petite décomposition de permutation à mon avis cherche les orbites des éléments de ta permutation ce qui te donnera sa décomposition en cycles et apès tu dois pouvoir en tirer aisément un produit minimal de transposition. A voir

[invitee3a2ba33]

Pour avoir la plus petite décomposition de permutation à mon avis cherche les orbites des éléments de ta permutation ce qui te donnera sa décomposition en cycles et apès tu dois pouvoir en tirer aisément un produit minimal de transposition. A voir

merci RoBeRTo-BeNDeR, je souhaite savoir où on peut trouver cet algorithme ?
Merci.

[invite332de63a]

Je ne sais pas tu peux tenter de le faire toi même si tu as un minimum de compétences en programmation sur logiciel de maths.
Du moins celui des orbites après celui pour mettre en transposition je ne vois pas trop comment le créer.
J'ai essayé hier d'en faire un pour les orbites sous Maple mais je n'y suis pas parvenu il y avait des petits bugs.

C'est que tu voudrais en faire quoi? Car je pense qu'à la main çà peut se faire, certes c'est pas des plus court.

[A voir en vidéo sur Futura]

[invitee3a2ba33]

Je ne sais pas tu peux tenter de le faire toi même si tu as un minimum de compétences en programmation sur logiciel de maths.
Du moins celui des orbites après celui pour mettre en transposition je ne vois pas trop comment le créer.
J'ai essayé hier d'en faire un pour les orbites sous Maple mais je n'y suis pas parvenu il y avait des petits bugs.

C'est que tu voudrais en faire quoi? Car je pense qu'à la main çà peut se faire, certes c'est pas des plus court.

merci, dt moi c koi une robite au juste : par exemple on a le vecteur (20,11,13,13,2,2,1,7) et on le trie par exemple on aura (1,2,2,7,11,13,13,20)
-------------------------------------------------------
(20,11,13,13,02,02,01,07)
(01,02,02,07,11,13,13,20)
----------------------------------------
c koi son orbite a cette permutation???
merci.

[Médiat]

Le langage SMS n'est pas autorisé sur ce forum, merci d'écrire vos messages en français !

Pour la modération

[invitee3a2ba33]

Le langage SMS n'est pas autorisé sur ce forum, merci d'écrire vos messages en français !

Pour la modération

Pardon MEDIATEUR vous avez raison et je ne dit pas le contraire cependant vous avez coupé l'harmonie de cette discution, il fallait me le dire en privé.
Merci.
______________________________ __________________________
"f dérivable donc f ' existe" dixit mon professeur de mathématiques.

[invite332de63a]

Je crois que l'on permutte plutôt les élément d'un groupe un par un enfin par exemple plaçons nous dans Z/5Z, on a comme élément 1,2,3,4,5.

La permutation s
( 1 2 3 4 5 ) qui permute 1 par 2, 2 par 1, 3 par 5, 4 par 3 et 5 par 4
( 2 1 5 3 4 )
L'orbite est la suite des image d'un élément du groupe (si je ne me trompe pas ) par exemple :

s(1)=2, s(2)=1 donc orbite(1)=orbite(2)={1,2}
s(3)=5, s(5)= 4 , s(4) = 3 donc orbite(3)=orbite(4)=orbite(5)= {3,5,4}

donc s se décompose en cycle de cette manière :

s=(1 2)o(3 5 4)

et donc en transposition comme ceci :

s=(1 2)o(3 5)o(4 5)

Donc pour ton vecteur...
départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)
(en supposant que le 1er 2 vas sur le 1er et le 2nd sur le 2nd, pareil pour le 13)

si on suppose que tu veux intervertir les coordonnées on va appeler ci la coordonnée i du vecteur donc la "permutation" que tu propose est (si l'on peut encore parler de permutation)

( c1 c2 c3 c4 c5 c6 c7 c8 ) = S
( c8 c5 c6 c7 c2 c3 c1 c4 )

d'orbites {c1 c8 c4 c7} {c2 c5} {c3 c6}

donc S=(c1 c8 c4 c7)o(c2 c5)o(c3 c6)
=(c1 c8)o(c8 c4)o(c4 c7)o(c2 c5)o(c3 c6)

Et il me semble peu probable qu'il y ai plus court

[Médiat]

Pardon MEDIATEUR vous avez raison et je ne dit pas le contraire cependant vous avez coupé l'harmonie de cette discution, il fallait me le dire en privé.
Merci.

La modération est publique, c'est la critique de la modération qui doit être privée.

Pour la modération

[invitee3a2ba33]

Je crois que l'on permutte plutôt les élément d'un groupe un par un enfin par exemple plaçons nous dans Z/5Z, on a comme élément 1,2,3,4,5.

La permutation s
( 1 2 3 4 5 ) qui permute 1 par 2, 2 par 1, 3 par 5, 4 par 3 et 5 par 4
( 2 1 5 3 4 )
L'orbite est la suite des image d'un élément du groupe (si je ne me trompe pas ) par exemple :

s(1)=2, s(2)=1 donc orbite(1)=orbite(2)={1,2}
s(3)=5, s(5)= 4 , s(4) = 3 donc orbite(3)=orbite(4)=orbite(5)= {3,5,4}

donc s se décompose en cycle de cette manière :

s=(1 2)o(3 5 4)

et donc en transposition comme ceci :

s=(1 2)o(3 5)o(4 5)

Donc pour ton vecteur...
départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)
(en supposant que le 1er 2 vas sur le 1er et le 2nd sur le 2nd, pareil pour le 13)

si on suppose que tu veux intervertir les coordonnées on va appeler ci la coordonnée i du vecteur donc la "permutation" que tu propose est (si l'on peut encore parler de permutation)

( c1 c2 c3 c4 c5 c6 c7 c8 ) = S
( c8 c5 c6 c7 c2 c3 c1 c4 )

d'orbites {c1 c8 c4 c7} {c2 c5} {c3 c6}

donc S=(c1 c8 c4 c7)o(c2 c5)o(c3 c6)
=(c1 c8)o(c8 c4)o(c4 c7)o(c2 c5)o(c3 c6)

Et il me semble peu probable qu'il y ai plus court

Merci RoBeRTo-BeNDeR t'es le meilleur,
mais dit moi une chose si on change cela '(en supposant que le 1er 2 vas sur le 1er et le 2nd sur le 2nd, pareil pour le 13)' est ce qu'on aura un résultat différent en longueur ? si c'est le cas le choix des transpositions doit suivre une loi ou quelque chose comme ça ?????
Merci une autre fois.

[invite332de63a]

Pour un cycle donné comme (1 2 3) on peut le décomposer comme ceci (1 2)o(2 3) et çà pour tous et c'est surement la méthode la plus "courte" en transposition pour définir une permutation.
De rien

[invitee3a2ba33]

Pour un cycle donné comme (1 2 3) on peut le décomposer comme ceci (1 2)o(2 3) et çà pour tous et c'est surement la méthode la plus "courte" en transposition pour définir une permutation.
De rien

Salut regarde ça :
départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)
______________________________ __________

( c1 c2 c3 c4 c5 c6 c7 c8 )
( c8 c5 c7 c6 c3 c2 c1 c4 )

(en supposant que le 1er 2 vas sur le 2nd et le 2nd sur le 1er, pareil pour le 13)
elle est juste cette permutation je crois?

maintenant les orbites : {c1 c8 c4 c6 c2 c5 c3 c7}
donc S = (c1 c8)o(c8 c4)o(c4 c6)o(c6 c2)o(c2 c5)o(c5 c3)o(c3 c7)
est ce que le choix de la transposition est important?
que pensez vous?
Merci

[invite332de63a]

Oui c'est juste à priori.
Ici tu as une permutation qui est déja un cycle.

Qu'entends tu par "est ce que le choix de la transposition est important?"

[invite332de63a]

Si ça t'interesse je viens de faire une procédure sous Maple qui donne les orbites d'une transposition.

[invitee3a2ba33]

Oui c'est juste à priori.
Ici tu as une permutation qui est déja un cycle.

Qu'entends tu par "est ce que le choix de la transposition est important?"

Salut, je vais vous expliquer mon problème :
______________________________
( c1 c2 c3 c4 c5 c6 c7 c8 )
( c8 c5 c6 c7 c2 c3 c1 c4 ) ce que vous avez écrit
______________________________
( c1 c2 c3 c4 c5 c6 c7 c8 )
( c8 c5 c7 c6 c3 c2 c1 c4 ) ce que j'ai écrit
______________________________

j'ai changé deux transpositions et l'orbite a changé, dans ce vecteur votre choix est le meilleur c'est évident mais si on a d'autres vecteurs où il y a plusieurs choix possibles de transpositions (permutation élémentaire de deux éléments) y a t'il un choix précis a faire pour avoir toujours la décomposition la plus courte? c'est ça ma question si vous avez compris.
Merci.

[invite332de63a]

Ah oui je comprend... à mon avis il faut privilégier des orbites plus courtes ... mais là votre problème est dû au fait que votre vecteur a plusieurs fois la même composante.
Je ne pense pas qu'il soit à priori facile de dire "celle-ci" se décrit en moins de transpositions que "celle-là" ... une étude doit être obligatoire.

Puis je vous demander pourquoi voulez vous cela (cet algorithme de décomposition en transpositions)?

[invitee3a2ba33]

Ah oui je comprend... à mon avis il faut privilégier des orbites plus courtes ... mais là votre problème est dû au fait que votre vecteur a plusieurs fois la même composante.
Je ne pense pas qu'il soit à priori facile de dire "celle-ci" se décrit en moins de transpositions que "celle-là" ... une étude doit être obligatoire.

Puis je vous demander pourquoi voulez vous cela (cet algorithme de décomposition en transpositions)?

Oui c'est ce que je crains, peut être on peut simplifier les orbites? ou quelque chose comme ça ? et ainsi arriver toujours au même résultat quelque soit le chemin qu'on prend qu'en pensez vous?
Pour l'utilisation de cet algorithme : pour trouver la signature d'une permutation donc il me faut le nombre minimum de transpositions.
Et si vous pouvez m'envoyer ton algorithme en Maple ça serai bien !!!!
Merci.

[invitebe0cd90e]

Salut,

1) tu n'as pas besoin d'avoir une ecriture minimale pour calculer la signature. Quand tu decomposes une permutation en produit de transpositions, peu importe comment, et peut importe lesquelles (cad que tu choisisses les (i,j) ou les (1,i)), le nombre de transposition change, mais pas la parité de ce nombre, et c'est seulement ca qui compte pour la signature.

2) il y a des moyens beaucoup plus directs pour calculer la signature, sauf erreur il suffit de decomposer la permutation en produit de cycle. En effet, la signature est un morphisme de groupe (donc la signature d'un produit est le produit des signatures), et un cycle est paire ssi sa longueur est impaire.

[invitee3a2ba33]

Salut,

1) tu n'as pas besoin d'avoir une ecriture minimale pour calculer la signature. Quand tu decomposes une permutation en produit de transpositions, peu importe comment, et peut importe lesquelles (cad que tu choisisses les (i,j) ou les (1,i)), le nombre de transposition change, mais pas la parité de ce nombre, et c'est seulement ca qui compte pour la signature.

2) il y a des moyens beaucoup plus directs pour calculer la signature, sauf erreur il suffit de decomposer la permutation en produit de cycle. En effet, la signature est un morphisme de groupe (donc la signature d'un produit est le produit des signatures), et un cycle est paire ssi sa longueur est impaire.

Oui je sais mais moi je la veux de cette façon c'est demandé comme ça et puis j'ai lu un article sur Wikipedia sur les permutations surtout la partie de la décomposition ; il y a un algorithme et ils disent qu'il donne la décomposition minimale mais je ne l'ai pas compris si vous pouvez m'aider là je vous serais reconnaissant.

[invitebe0cd90e]

Si tu parles de ca : http://fr.wikipedia.org/wiki/Permuta....A9composition je ne vois pas trop ce qui te pose probleme, l'algorithme est archi simple, et en effet il me semble qu'il donne bien la decomposition minimale.

- tu prends une permutation s
- tu cherches le plus petit entier i tel que s(i) est different de i
- tu appelles t la transposition (i,s(i))
- tu appelles s1 la permutation ts
- tu recommences l'algorithme avec s1, en commencant evidemment a chercher le plus petit entier non fixé par s1 a partir de i+1 et non de 1.

[invite332de63a]

Exactement comme jobherzt, si vous vouliez la signature alors ceci n'est pas très compliqué effectivement, aucunement besoin des transpositions, même si souvent on peut l'introduire grâce à elle.
Si vous avez une permutation de signature 1 alors elle ne peut se décomposer qu'en un produit pair de transpositions et inversement pour -1.
Donc nullement besoin de savoir que il en faut 4 ou 6 ou 8 ou plus ce sera toujours une signature de 1.
sinon pour savoir les signature la méthode utilisée par Ian Stewart dans "Oh! Les beaux groupes" à le goût d'être simple, rapide et "graphique"!
Ecrivez votre permutation comme je vous l'ai mis plus haut et tracez des traits (droits ou courbés) entre les même nombres et comptez ensuite le nombre d'intersections entre ces traits et si il en a un nombre pair alors la signature est 1 sinon -1.
Mais si c'est pour mettre sur ordi... privilégiez plutôt une approche plus directe.

Voici ma procédure pour les orbites:

Delet:=proc(L,n)
> local m,v,i;global L1:
> m:=nops(L):v:=0:
> for i to m do
> if op(i,L)=n then v:=i:m:=i: fi: od:
> if v<>0 then L1:=subsop(v=NULL,L):else L1:=L:fi:
> end:

(celle ci supprime le premier élément de valeur n dans une liste si il en existe un, sinon ne fait rien)

Orb:=proc(L)
> local L2,f,m,Li,p:global Lt:
> Lt:={};L2:=[seq(i,i=1..nops(L))]:
> f:=i->op(i,L):
> while nops(L2)>0 do
> m:=op(1,L2):
> Delet(L2,m):L2:=L1:
> Li:=[m]: p:=f(m):
> Delet(L2,p);L2:=L1:
> while p<>m do
> Li:=[op(Li),p]: p:=f(p):
> Delet(L2,p):L2:=L1:
> od:
> Lt:={op(Lt),Li}: od:
> print(Lt):
> end:

(elle nécessite la 1ère pour fonctionner, vous rentrez seulement la partie image de votre permutation et sans fantaisie ^^ du genre L:=[1,3,5,4,2] avec tous les nombres de 1 à votre maximum)

Voilà

[invitee3a2ba33]

Si tu parles de ca : http://fr.wikipedia.org/wiki/Permuta....A9composition je ne vois pas trop ce qui te pose probleme, l'algorithme est archi simple, et en effet il me semble qu'il donne bien la decomposition minimale.

- tu prends une permutation s
- tu cherches le plus petit entier i tel que s(i) est different de i
- tu appelles t la transposition (i,s(i))
- tu appelles s1 la permutation ts
- tu recommences l'algorithme avec s1, en commencant evidemment a chercher le plus petit entier non fixé par s1 a partir de i+1 et non de 1.

Salut, ici i c'est un indice ou une valeur? si c'est l'indice alors cet algorithme ne donne pas la permutation minimale toujours, sinon expliquez moi avec un exemple où il y a plusieurs éléments répétés si vous voulez.
Merci.

[invitebe0cd90e]

Ca veut dire quoi une valeur ? et qu'appelles tu un exemple avec plusieurs elements repetés ?

Une permutation c'est une bijection de l'ensemble {1,..,n} dans lui meme, et ici i est un element de cet ensemble, et s(i) l'image de cet element par s.

Pour ce qui est de l'exemple ca depend comment tu "connais" une permutation, si c'est sous une forme particuliere (genre produit de cycle) il n'y aura essentiellement rien a faire. Donne moi une permutation qui te pose probleme et on verra.

[invitee3a2ba33]

Exactement comme jobherzt, si vous vouliez la signature alors ceci n'est pas très compliqué effectivement, aucunement besoin des transpositions, même si souvent on peut l'introduire grâce à elle.
Si vous avez une permutation de signature 1 alors elle ne peut se décomposer qu'en un produit pair de transpositions et inversement pour -1.
Donc nullement besoin de savoir que il en faut 4 ou 6 ou 8 ou plus ce sera toujours une signature de 1.
sinon pour savoir les signature la méthode utilisée par Ian Stewart dans "Oh! Les beaux groupes" à le goût d'être simple, rapide et "graphique"!
Ecrivez votre permutation comme je vous l'ai mis plus haut et tracez des traits (droits ou courbés) entre les même nombres et comptez ensuite le nombre d'intersections entre ces traits et si il en a un nombre pair alors la signature est 1 sinon -1.
Mais si c'est pour mettre sur ordi... privilégiez plutôt une approche plus directe.

Voici ma procédure pour les orbites:

Delet:=proc(L,n)
> local m,v,i;global L1:
> m:=nops(L):v:=0:
> for i to m do
> if op(i,L)=n then v:=i:m:=i: fi: od:
> if v<>0 then L1:=subsop(v=NULL,L):else L1:=L:fi:
> end:

(celle ci supprime le premier élément de valeur n dans une liste si il en existe un, sinon ne fait rien)

Orb:=proc(L)
> local L2,f,m,Li,p:global Lt:
> Lt:={};L2:=[seq(i,i=1..nops(L))]:
> f:=i->op(i,L):
> while nops(L2)>0 do
> m:=op(1,L2):
> Delet(L2,m):L2:=L1:
> Li:=[m]: p:=f(m):
> Delet(L2,p);L2:=L1:
> while p<>m do
> Li:=[op(Li),p]: p:=f(p):
> Delet(L2,p):L2:=L1:
> od:
> Lt:={op(Lt),Li}: od:
> print(Lt):
> end:

(elle nécessite la 1ère pour fonctionner, vous rentrez seulement la partie image de votre permutation et sans fantaisie ^^ du genre L:=[1,3,5,4,2] avec tous les nombres de 1 à votre maximum)

Voilà

Merci pour ton programme c'est bien, mais pourquoi donc cette procedure pour supprimer la répétition ? nous travaill dans le cas général car si chaque élément est unique le travail sera facile; en effet chaque élément ira dans sa place seule à lui et il y aura une seule permutation minimale (en ignorant le changement d'ordre de transpositions dans cette même permutation car les transpositions dans ce cas sont indépendantes les unes des autres) donc le problème est dans le cas où il y a des valeurs répétées.
Merci.

[invite332de63a]

La procédure pour supprimé ne valeur est utilisée pour enlevé un à un les éléments de l'orbite de la liste 1..n, comme par exemple 1 et 2 peuvent avoir la même orbite je ne vais pas faire répéter la procédure de 1 pour 2.
De plus l'ordinateur ne comprend pas que [1,2,5,8]=[2,5,8,1] en terme d'orbite donc c'est plus simple de ne les traiter qu'un fois.

Je tenterai de faire une procédure dépendante de "Orb" pour te donner "ma" décomposition minimale enfin je suppose que çà l'est

Et de rien pour la procédure ^^

[invitee3a2ba33]

Ca veut dire quoi une valeur ? et qu'appelles tu un exemple avec plusieurs elements repetés ?

Une permutation c'est une bijection de l'ensemble {1,..,n} dans lui meme, et ici i est un element de cet ensemble, et s(i) l'image de cet element par s.

Pour ce qui est de l'exemple ca depend comment tu "connais" une permutation, si c'est sous une forme particuliere (genre produit de cycle) il n'y aura essentiellement rien a faire. Donne moi une permutation qui te pose probleme et on verra.

Salut, regarde ça :
départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)
c'est une permutation ça, une simple permutation (le tri), je veux sa décompsition la plus minimale en produit de transpositions, si vous savez comment faire dites le moi.

[invitee3a2ba33]

La procédure pour supprimé ne valeur est utilisée pour enlevé un à un les éléments de l'orbite de la liste 1..n, comme par exemple 1 et 2 peuvent avoir la même orbite je ne vais pas faire répéter la procédure de 1 pour 2.
De plus l'ordinateur ne comprend pas que [1,2,5,8]=[2,5,8,1] en terme d'orbite donc c'est plus simple de ne les traiter qu'un fois.

Je tenterai de faire une procédure dépendante de "Orb" pour te donner "ma" décomposition minimale enfin je suppose que çà l'est

Et de rien pour la procédure ^^

Salut, comment dire : pouvez vous l'écrire en C ou en Pascal ou donner l'algorithme car je comprends que vaguement cette syntaxe.
Merci.

[invite332de63a]

Non je ne peux pas car moi même je ne connais pas ces format d'écriture genre C ou Pascal... je n'utilise que Maple ce qui est déja bien suffisant!

[invitee3a2ba33]

Non je ne peux pas car moi même je ne connais pas ces format d'écriture genre C ou Pascal... je n'utilise que Maple ce qui est déja bien suffisant!

Salut, je vais écrire moi cet algorithme alors et on va comparer les résultats.

[invite332de63a]

ok Klinterman