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.

[JeitEmgie]

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

oui, mais il ne donne probablement pas la plus petite liste de permutations nécessaires… (d'abord ce sera "une des" … et non "la"…)

parce que dans l'énoncé, les listes ont des éléments en plusieurs exemplaires…
et comme l'algorithme choisit la première possibilité… il n'y a aucune raison a priori de générer la liste la plus courte…
on peut déjà l'améliorer en donnant priorité aux permutations "parfaites" : celles qui mettent les 2 éléments à la bonne place…

[pseudocode]

oui, mais il ne donne probablement pas la plus petite liste de permutations nécessaires… (d'abord ce sera "une des" … et non "la"…)

Ah. Je n'ai regardé que le code de l'algo et pas ta question.

Oui effectivement ca donne "une" liste de transpositions, mais pas nécessairement la plus petite. Il n'existe pas (a ma connaissance) d'algo pour obtenir cette liste.

Tu peux regarder du coté des "Breakpoint Graph" pour avoir des algos qui donnent des "plus petites" listes de transpositions. Mais ca ne donne pas l'optimale non plus.

[Onimaru]

En effet dans l'algorithme que j'ai écrit si on change la boucle :
"for J := I + 1 to N do" en "for J := N downto I + 1 do" on obtient presque toujours un résultat plus optimal.

Donc selon vous cet algorithme n'existe pas ?

Et si on essaye avec les orbites?

[JeitEmgie]

En effet dans l'algorithme que j'ai écrit si on change la boucle :
"for J := I + 1 to N do" en "for J := N downto I + 1 do" on obtient presque toujours un résultat plus optimal.

hasard du jeu de données…

le seul moyen simple d'améliorer vite fait l'algorithme sur l'aspect du nombre de permutations, est de commencer par les permutations "parfaites" : celles qui mettent les 2 valeurs à la bonne place en une seul permutation…
(s'il y en a…)

[pseudocode]

Et si on essaye avec les orbites?

C'est justement le principe du "Breakpoint Graph"

[Onimaru]

Pouvez me donnez cet algorithme qui permet de commencer par les permutations "parfaites" ?
Et dites moi que pensez vous des orbites?

[Onimaru]

Et pouvez vous me dire plus sur "Breakpoint Graph" ?

[pseudocode]

Et pouvez vous me dire plus sur "Breakpoint Graph" ?

Je n'en sais pas beaucoup plus que ce qu'en dit la littérature. C'est utilisé pour réarranger la structure d'un génome. L'idée générale est de relier les elements entre eux suivant une relation d'ordre, et de "démêler" les croisements dans le graphe ainsi obtenu.

Je n'ai jamais implémenté ce algorithme, donc je n'ai pas grand chose à en dire.

[JeitEmgie]

Pouvez me donnez cet algorithme qui permet de commencer par les permutations "parfaites" ?

commencer par les permutations "parfaites" c'est juste déboubler la boucle intérieure…

et modifier le test en

"SI Source[i] = Destination[j] ET Source[j] = Destination[i] ALORS SWAP"

dans la première boucle, l'autre restant la même
comme çà à chaque "tour" du "tant que non fini"… on permute d'abord les paires qui mettent 2 éléments à leur place…

(cela si on ne coupe pas les cheveux en quatre… car on pourrait dire que chaque permutation non parfaite a peut-être créé une parfaite qui n'existait pas avant… dans ce cas il faut arrêter la deuxième boucle dès qu'un swap a lieu pour recommencer au début du "tant que non fini" par la recherche des parfaites…)…

[Onimaru]

Merci JeitEmgie, désolé pour la question mais pouvez vous me dire exactement comment l'implémenter dans mon algorithme ?
et merci d'avance.

[Onimaru]

Voici l'algorithme modifié :

Code pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
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]) et (B[J] = T[I]) then // privilégier les permutations 
                                                      // parfaites. 
      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;
///////////////////////////////////////////////////////////////////////////////
 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 // les permutations restantes (composées).
      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;

[Onimaru]

Je n'en sais pas beaucoup plus que ce qu'en dit la littérature. C'est utilisé pour réarranger la structure d'un génome. L'idée générale est de relier les elements entre eux suivant une relation d'ordre, et de "démêler" les croisements dans le graphe ainsi obtenu.

Je n'ai jamais implémenté ce algorithme, donc je n'ai pas grand chose à en dire.

En effet j'ai entendu parler d'une chose pareille, il parait qu'ils utilisent la distance entre les permutations pour pouvoir transformer une chaîne d'ADN en une autre pour chercher à comprendre les mutations génétiques.

Donc on peut résumer ce problème comme ça :

1) Deux tableaux A et B, B est obtenu par une permutation des éléments de A, on cherche une des permutations minimales qui transforment A en B.

2) Il y a des problèmes (ce que je sais) :

A) Les points fixes : il faut les éviter dans la recherche.

B) Les éléments répétés posent des problèmes dans le choix des
transpositions :
i) Il faut commencer par les transpositions parfaites (JeitEmgie).
ii) Ensuite continuer avec les transpositions restantes.
iii) Il doit y avoir une méthode pour simplifier certaines transpositions.

3) ?

Manque t il quelque chose ?

[JeitEmgie]

iii) Il doit y avoir une méthode pour simplifier certaines transpositions.

si la seule opération qui vous est permise est la transposition, qu'entendez-vous par simplification ?

(si vous introduisez des rotations… on ouvre une porte…)

[Onimaru]

Je veux dire une transposition équivalente à deux transpositions et c'est la seule opération permise.

Code pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
 T := A;
 I := 1;
 while I <= N do
  begin
   Quit := false;
   if B[I] <> T[I] then
    begin
     for J := 1 to N do
      if B[J] <> T[J] then
       for K := J + 1 to N do
        if (B[J] = T[K]) and (B[K] = T[J]) then
         begin
          Quit := true;
          AddTransposition(AsTransposition(J, K));
          Swap(T, AsTransposition(J, K));
          Break
         end;
      if not Quit then
       for J := I + 1 to N do
        if B[I] = T[J] then
         begin
          AddTransposition(AsTransposition(I, J));
          Swap(T, AsTransposition(I, J));
          Break
         end
    end;
   Inc(I)
  end;

Voici une version modifiée qui prends en compte ce que vous avez dit mais il y a un problème dans le résultat il est un peu faux.

Pouvez vous m'aider?