Décomposition des permutations

[invitebe0cd90e]

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

Pas vraiment vu que ce tri ne correspond pas de facon unique a une permutation. Pour lui associer la permutation qui aura la longueur la plus courte, il suffit de garder les doublons dans l'ordre ou ils sont (cad associer au premier 13 du haut le premier 13 du bas, etc..). Sinon effectivement tu vas rajouter des transpositions. Mais du coup notes que meme la notion de signature n'est pas bien definie puisque les deux permutations possible pour obtenir ce tri differe sauf erreur d'exactement une transposition, donc elles ont des signatures opposées.
-----

[invitee3a2ba33]

Pas vraiment vu que ce tri ne correspond pas de facon unique a une permutation. Pour lui associer la permutation qui aura la longueur la plus courte, il suffit de garder les doublons dans l'ordre ou ils sont (cad associer au premier 13 du haut le premier 13 du bas, etc..). Sinon effectivement tu vas rajouter des transpositions. Mais du coup notes que meme la notion de signature n'est pas bien definie puisque les deux permutations possible pour obtenir ce tri differe sauf erreur d'exactement une transposition, donc elles ont des signatures opposées.

salut, vous voulez dire comme ça:
départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)

[invitebe0cd90e]

C'est ca, en laissant les 13 dans l'ordre ou ils apparaissent tu minimise le nombre de permutations. L'autre possibilité revient exactement a :
- appliquer cette permutation
- puis echanger les deux 13

donc ca rajoute exactement une transposition (et donc notes que ca change la signature de la permutation !)

[invitee3a2ba33]

C'est ca, en laissant les 13 dans l'ordre ou ils apparaissent tu minimise le nombre de permutations. L'autre possibilité revient exactement a :
- appliquer cette permutation
- puis echanger les deux 13

donc ca rajoute exactement une transposition (et donc notes que ca change la signature de la permutation !)

Merci et pardonne moi pour cette question êtes vous sure que ça marche toujours comme ça?

[invitebe0cd90e]

Oui, faire autrement revient a composer une permutation par une ou plusieurs transpositions qui n'apparaissent pas dans la permutation precedente par definition, donc ca rallonge forcement..

[invitee3a2ba33]

Oui, faire autrement revient a composer une permutation par une ou plusieurs transpositions qui n'apparaissent pas dans la permutation precedente par definition, donc ca rallonge forcement..

Merci pour l'explication tu m'as aidé, donc pour n'importe qu'elle permutation, pas forcémént un tri, on obtient la permutation minimale comme ça?

[invitebe0cd90e]

J'en suis quasiment sur, en effet.

[invitee3a2ba33]

J'en suis quasiment sur, en effet.

Merci beaucoup

[invitebe0cd90e]

Mais au risque d'insister, aies conscience que des que tu as des doublons tu as plusieurs permutations associées, donc ca n'a pas de sens de parler de "decomposition minimale", plutot de "permutation qui admet la decomposition minimale, minimale parmi les permutations possibles"

[invitee3a2ba33]

Mais au risque d'insister, aies conscience que des que tu as des doublons tu as plusieurs permutations associées, donc ca n'a pas de sens de parler de "decomposition minimale", plutot de "permutation qui admet la decomposition minimale, minimale parmi les permutations possibles"

Oui je sais que le problème réside dans les éléments répétés sinon le travail sera facile : chaque élément ira à ça place bien destinée à lui, maintenant ce que je cherche c'est décomposition minimale en transopositions d'une permutation donnée car chaque permutation admet une infinité des décompositions.
Donc je veux la méthode générale pour faire ce travail et d'après ce que j'ai compris de cette discution instructive on fait comme suit:
* On cherche les orbites des éléments, si des éléments sont répétés on prend toujours les positions dans l'ordre.
* On fait extraire les transpositions.
C'est ça ?

[invitebe0cd90e]

Je crois que tu n'as pas compris. Les repetitions ca n'est pas juste un "probleme", ca ne rend pas simplement la question plus compliqué. Je le repete encore une fois, quand tu dis :

maintenant ce que je cherche c'est décomposition minimale en transopositions d'une permutation donnée

c'est un non sens, parce que quand tu as des repetitions tu as plusieurs permutations possibles. Donc encore une fois, ce que je te donne c'est, parmi ces permutations possibles, celle qui aura la decomposition la plus courte. Mais telle quelle, quand on connait ton probleme par ailleurs, ta phrase n'a pas de sens.

Et desolé de le repeter encore, du coup la notion meme de signature n'a pas de sens dans ton cas...

[invitee3a2ba33]

Je crois que tu n'as pas compris. Les repetitions ca n'est pas juste un "probleme", ca ne rend pas simplement la question plus compliqué. Je le repete encore une fois, quand tu dis :



c'est un non sens, parce que quand tu as des repetitions tu as plusieurs permutations possibles. Donc encore une fois, ce que je te donne c'est, parmi ces permutations possibles, celle qui aura la decomposition la plus courte. Mais telle quelle, quand on connait ton probleme par ailleurs, ta phrase n'a pas de sens.

Et desolé de le repeter encore, du coup la notion meme de signature n'a pas de sens dans ton cas...

Désolé mais ma phrase a un sens,

regarde ça :

départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)

ça c'est une permutation(ici par exemple un tri) c'est ça la donnée,
moi je veux décomposer cette permutation en produit de transpositions (permutatation 'atomique' de deux éléments et je crois que vous le savez),
En ce qui concerne la décomposition il y en a une infinité (je peux transposer deux éléments et refaire le même chose ce qui les annulent, je peux permuter deux éléments identiques, ...).
Donc je cherche la décomposition qui contient le nombre minimale de de transpositions, je ne sais pas si elle est unique ou non mais une d'elles me suffit.

En ce qui concerne la signature c'est un autre problème.

[invitebe0cd90e]

Désolé mais ma phrase a un sens,

regarde ça :

départ (20,11,13,13,02,02,01,07)
arrivée (01,02,02,07,11,13,13,20)

ça c'est une permutation

Desolé mais non, justement, ce que je repete depuis.. un bail c'est que ton tri ne definit pas une permutation de facon unique. Il existe plusieurs permutations distinctes qui te donnent le meme tri, donc je regarde et je confirme : ca n'est pas une permutation.

[invitee3a2ba33]

Desolé mais non, justement, ce que je repete depuis.. un bail c'est que ton tri ne definit pas une permutation de facon unique. Il existe plusieurs permutations distinctes qui te donnent le meme tri, donc je regarde et je confirme : ca n'est pas une permutation.

Non c'est une seule permutation mais elle admet plusieurs décompostions, c'est ça la phrase la plus juste, évitons de parler du tri regarde ça:

départ (20,11,13,13,02,02,01,07)
arrivée (11,13,13,20,01,02,02,07)

ça ce n'est pas un tri c'est une permutation quelconque, selon vous ce n'est pas une permutation unique c'est ça ???

[invitebe0cd90e]

Noooon, c'est plusieurs permutations, c'est un fait c'est tout...

Si tu n'es pas convaincu prend un exemple simple, sinon on ne va pas aller loin...

(5,5,3) donne (3,5,5).

Il y deux permutations qui donnent ca, a savoir :

(1,2,3) -> (3,1,2)
(1,2,3) -> (3,2,1)

ces deux permutations sont vraiment, vraiment, vraiment deux permutations différentes. La notion de permutation n'est bien definie pour des objets distincts. Ici, comme les deux 5 sont interchangeables sans pour autant changer le resultat, on a plusieurs permutations qui donnent le meme resultat. Point.

[invitebe0cd90e]

Ceci dit, j'avoue m'etre trompé sur un point : garder les doblons dans leur ordre ne donne pas forcement la permutation minimale s'il existe des points fixes. Bref, dans ce cas :

- la premiere permutation est le produit (1,2)(2,3), donc de signature 1
- la seconde est la permutation (1,3) donc de signature -1.

Donc la signature n'est pas bien definie non plus.

[invitee3a2ba33]

Ceci dit, j'avoue m'etre trompé sur un point : garder les doblons dans leur ordre ne donne pas forcement la permutation minimale s'il existe des points fixes. Bref, dans ce cas :

- la premiere permutation est le produit (1,2)(2,3), donc de signature 1
- la seconde est la permutation (1,3) donc de signature -1.

Donc la signature n'est pas bien definie non plus.

Vous avez raison ce sont plusieurs permutations, mais dit moi comment trouver la minimale alors?

[invitee3a2ba33]

Vous avez raison ce sont plusieurs permutations, mais dit moi comment trouver la minimale alors?

Et pour les points fixes, faut il les éviter ?