Discussion :

[Onimaru]

Salut à tous je cherche un algorithme qui permet de trouver la permutation minimale qui transforme le vecteur A en B puis donne la décomposition minimale de cette permutation en produit de transpositions.

Exemple (tri) :

A : (4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2)
B : (0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4)

Merci.

[pseudocode]

C'est un énoncé d'exercice, ou ca a une quelconque finalité (qu'on aimerait bien connaitre) ?

[Onimaru]

Salut
Tout a commencé quand je lisais l'article sur les permutations dans Wikipedia, plus précisément la partie décomposition des permutations en transpositions, je n'ai pas compris cet algorithme.

[pseudocode]

Salut
Tout a commencé quand je lisais l'article sur les permutations dans Wikipedia, plus précisément la partie décomposition des permutations en transpositions, je n'ai pas compris cet algorithme.

Et bien le but est de trouver une suite de permutation (echange de 2 elements) qui transforme A en B.

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, puis cherche dans les elements restant celui qu'il faudrait mettre.
2. L'algo effectue la permutation (et la note en mémoire).
3. retour à l'étape 1, tant que A est différent de B

Au final, on obtient la liste des permutations a effectuer pour transformer A en B

[Onimaru]

Merci pour ton aide,
Pour ne pas confondre les termes : la permutation est un ensemble de transpositions (permutation à deux) c'est comme ça?

D'après ce que j'ai compris voici l'algorithme :
(A, B les deux vecteurs en entrée, T vecteur temporaire pour générer la permutation).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 T := A; 
 for I := 1 to N do
  if B[I] <> T[I] then // pour laisser les points fixes.
   for J := I + 1 to N do // on cherche la première position qui satisfait la 
                                // condition.
     if B[I] = T[J] then
      begin
       AddTransposition(AsTransposition(I, J)); // ajouter cette transposition à 
                                                              // la permutation.
       Swap(T, AsTransposition(I, J)); // Modifier le vecteur temporaire.
       Break // pour ne pas ajouter une autre transposition pour le même 
               // élément.
      end;

Dites moi si mon algorithme est juste et si c'est le cas est ce qu'il donne la plus petite permutation qui transforme A en B ?
Merci.

[pseudocode]

Oui, cela m'a l'air d'être bon.

[Nemerle]

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, puis cherche dans les elements restant celui qu'il faudrait mettre.
2. L'algo effectue la permutation (et la note en mémoire).
3. retour à l'étape 1, tant que A est différent de B

Cet algo est correct dans le monde des permutations. Les gars, utilisons le langage standard:

- une permutation est une bijection de (1...n) vers (1...n)
- une transposition t(i,j) est la bijection switchant i et j et fixant le reste.

L'algo décrit par Pseudocode fournit une décomposition minimale d'une permutation en composition de transpositions. C'est minimal, au sens où c'est le job "minimum", comme on le voit avec la représentation en tresse des permutations ci-dessous (désolé, je dessine mal).




Donc ton exemple tu recherches une décomposition en transpositions te permettant de passant de ton vecteur A à B. Ok, c'est pas le monde des permutations, car des composantes de A et/ou B sont égales, mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".

[Onimaru]

Ton idée parait intéressante et je crois c'est que je cherche pouvez vous l'écrire sous forme d'algorithme ? et moi de ma part je vais essayer.

[pseudocode]

mais Pseudo a adapté l'algo.Je pense qu'une précision s'impose dans son point 1:

1. L'algo cherche le premier element de A (de gauche a droite) qui n'est pas identique a celui de B, soit Ai<>Bi, puis cherche dans les elements Aj ou j>i le premier élément vérifiant Aj=Bi et Bj<>Aj. On applique alors la transposition T(i,j), et comme dans le dessin ci-dessus on arrive à une décomposition "minimale".

Oui, mon explication n'était pas très rigoureuse mathématiquement parlant. J'essayais juste de résumer le principe de l'algo de Wikipedia en 3 phrases.

Ca m'apprendra.