Discussion :

[Onimaru]

(3,0,4,2,3,1,4,2,1)
(0,1,1,2,2,3,3,4,4)

0) From : 0 ,To : 1
1) From : 1 ,To : 8
2) From : 2 ,To : 5
3) From : 4 ,To : 7
4) From : 5 ,To : 8
5) From : 6 ,To : 7
------------------------------------

0) From : 8 ,To : 2
1) From : 1 ,To : 5
2) From : 5 ,To : 0
3) From : 7 ,To : 6
4) From : 6 ,To : 4
------------------------------------

0) From : 0 ,To : 1
1) From : 1 ,To : 5
2) From : 2 ,To : 8
3) From : 4 ,To : 7
4) From : 6 ,To : 7

//////////////////////////////////////

(4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2)
(0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4)

0) From : 0 ,To : 2
1) From : 1 ,To : 17
2) From : 2 ,To : 16
3) From : 3 ,To : 7
4) From : 4 ,To : 6
5) From : 6 ,To : 20
6) From : 7 ,To : 12
7) From : 9 ,To : 20
8) From : 12 ,To : 18
9) From : 14 ,To : 17
------------------------------------

0) From : 16 ,To : 3
1) From : 18 ,To : 9
2) From : 2 ,To : 7
3) From : 7 ,To : 20
4) From : 20 ,To : 14
5) From : 14 ,To : 4
6) From : 4 ,To : 17
7) From : 17 ,To : 0
8) From : 1 ,To : 6
9) From : 6 ,To : 12
------------------------------------

0) From : 0 ,To : 2
1) From : 1 ,To : 6
2) From : 2 ,To : 7
3) From : 3 ,To : 16
4) From : 4 ,To : 17
5) From : 6 ,To : 12
6) From : 7 ,To : 20
7) From : 9 ,To : 17
8) From : 14 ,To : 18

//////////////////////////////////////

(1,1,1,3,0,4,1,2,2,2)
(0,1,1,1,1,2,2,2,3,4)

0) From : 0 ,To : 4
1) From : 3 ,To : 6
2) From : 5 ,To : 9
3) From : 6 ,To : 8
------------------------------------

0) From : 4 ,To : 0
1) From : 9 ,To : 5
2) From : 6 ,To : 8
3) From : 8 ,To : 3
------------------------------------

0) From : 0 ,To : 4
1) From : 3 ,To : 6
2) From : 5 ,To : 8
3) From : 6 ,To : 9
4) From : 8 ,To : 9

Les résultats des trois algorithmes sur trois paires de tableaux (A et B, B = A trié)

1) Les première partie : le premier algorithme avec la boucle pour descendante.

2) La deuxième partie : avec les orbites en prenant en considération au premier lieu les transpositions parfaites.

3) La troisième partie : avec l'algorithme de Nemerle.

Que peut on conclure?

[Nemerle]

Que peut on conclure?

[EDIT] j'ai supprimé une connerie écrite trop vite ... [/EDIT]

[Onimaru]

Voici ma transcription de ton code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
 T := A;
 I := 0;
 while I <> N - 1 do
  begin
   if T[I] <> B[I] then
    begin
     J := I + 1;
     while (T[J] <> B[I]) or (T[J] = B[J]) do
      Inc(J);
     AddTransposition(AsTransposition(I, J));
     Swap(T, AsTransposition(I, J))
    end;
   Inc(I)
  end;

T qui remplace A pour le conserver,
N la taille de A et B et T
Le premier indice est 0 dans mon cas.

[Nemerle]

Que peut on conclure?

Entre autre... ça explique que j'ai écrit une connerie: le fait que tu as des doublons dans tes coordonnées de A & B ne guarantit plus que l'algo de Pseudocode (vous voyez, je ne dit plus le mien ) ne fournit plus l'optimal: dans l'exemple 3, l'algo fournit la décomposition

(89)°(69)°(58)°(36)°(04)

Mais (89)°(69)°(58) = (68)°(59), donc la décomposition la plus courte est bien en 4 transpositions.

De la même manière, on voit que les 2 autres méthodes ne guarantissent pas l'optimalité non plus...


Il faut réfléchir plus avant... rapidement, je pense qu'il faut ajouter à "mon" algo une étape supplémentaire: une fois la liste des transpostions identifées, il faut repasser de la gauche vers la droite pour simplifier en utilisant les identités fondamentales des transpositions (voir Groupe de Coxeter).

On verra lundi...

[Onimaru]

Entre autre... ça explique que j'ai écrit une connerie: le fait que tu as des doublons dans tes coordonnées de A & B ne guarantit plus que l'algo de Pseudocode (vous voyez, je ne dit plus le mien ) ne fournit plus l'optimal: dans l'exemple 3, l'algo fournit la décomposition

(89)°(69)°(58)°(36)°(04)

Mais (89)°(69)°(58) = (68)°(59), donc la décomposition la plus courte est bien en 4 transpositions.

De la même manière, on voit que les 2 autres méthodes ne guarantissent pas l'optimalité non plus...


Il faut réfléchir plus avant... rapidement, je pense qu'il faut ajouter à "mon" algo une étape supplémentaire: une fois la liste des transpostions identifées, il faut repasser de la gauche vers la droite pour simplifier en utilisant les identités fondamentales des transpositions (voir Groupe de Coxeter).

On verra lundi...

Pouvez vous nous dire plus sur (89)°(69)°(58) = (68)°(59) ou la réduction car je crois c'est elle qui vas nous sortir de ce problème?

[Onimaru]

J'ai lu sur wikipedia un article sur les groupes de Coxeter :
http://fr.wikipedia.org/wiki/Groupe_de_Coxeter

Il parle des permutation et des transpositions mais je n'ai pas saisi le sens, qu'en pensez vous?

[JeitEmgie]

En traitant en priorité les permutations idéales :

Exemple 1: 5 permutations,
Exemple 2 : 9 permutations,
Exemple 3 : 4 permutations,

Pour

Code :

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

1
2
3
 
{ 3,0,4,2,3,1,4,2,1 }
{ 0,1,1,2,2,3,3,4,4 }

résultat

Code :

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

1
2
3
4
5
6
 
from 2 to 8
from 0 to 1
from 1 to 5
from 4 to 7
from 6 to 7

Pour

Code :

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

1
2
3
 
{ 4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2 } ;
{ 0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4 } ;

résultat

Code :

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

1
2
3
4
5
6
7
8
9
10
 
from 3 to 16
from 9 to 18
from 0 to 2
from 2 to 17
from 1 to 6
from 6 to 12
from 4 to 7
from 7 to 20
from 14 to 20

Pour

Code :

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

1
2
3
 
{ 1,1,1,3,0,4,1,2,2,2 } 
{ 0,1,1,1,1,2,2,2,3,4 }

résultat

Code :

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

1
2
3
4
5
 
from 0 to 4
from 5 to 9
from 3 to 6
from 6 to 8

[Onimaru]

Merci JeitEmgie,
Pouvez vous nous donnez l'algorithme pour l'implémenter et faire une étude comparative des méthodes qu'on a.
Suivant votre conseille j'ai fait la même chose en privilégiant les permutations idéales mais en utilisant les orbites : le deuxième résultat de chaque essai.
mais votre méthode le fait en moins de permutations on le voit avec l'exemple 2
avec 9 transpositions seulement contre 10 pour les algorithmes 1 et 2.

[Onimaru]

Le résultat de JeitEmgie :

0) from 3 to 16
1) from 9 to 18
2) from 0 to 2
3) from 2 to 17
4) from 1 to 6
5) from 6 to 12
6) from 4 to 7
7) from 7 to 20
8) from 14 to 20

Le résultat avec les cycles et prise en charge des permutations idéales :

0) From : 16 ,To : 3
1) From : 18 ,To : 9

2) From : 2 ,To : 7
3) From : 7 ,To : 20
4) From : 20 ,To : 14
5) From : 14 ,To : 4
6) From : 4 ,To : 17
7) From : 17 ,To : 0

8) From : 1 ,To : 6
9) From : 6 ,To : 12

Les deux premières transpositions sont identiques :
0) From : 16 ,To : 3
1) From : 18 ,To : 9

on peut faire descendre deux permutations en bas sans changer le résultat :

0) from 3 to 16
1) from 9 to 18

2) from 0 to 2
3) from 2 to 17
4) from 4 to 7
5) from 7 to 20
6) from 14 to 20

7) from 1 to 6
8) from 6 to 12

On peut voir que le cycle :
2) From : 2 ,To : 7
3) From : 7 ,To : 20
4) From : 20 ,To : 14
5) From : 14 ,To : 4
6) From : 4 ,To : 17
7) From : 17 ,To : 0

a été modifié en :

2) from 0 to 2
3) from 2 to 17
4) from 4 to 7
5) from 7 to 20
6) from 14 to 20

pour pouvoir se débarrasser d'une transposition, c'est ça que j'appelle la réduction, qu'en pensez vous?

[Onimaru]

Voici l'algorithme qui donne les résultats de JeitEmgie :

Code :

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
30
31
32
33
34
35
 
 
 T := A; // Tableau temporaire.
 // Mask un tableau de booléens.
 for I := 0 to N - 1 do
  Mask[I] := A[I] <> B[I]; // Initialiser Mask pour éviter les points fixes.
 
 for I := 0 to N - 1 do // Boucle principale.
  if Mask[I] then // Éviter les points traités et les points fixes.
   begin
///////////////////////////////////////////////////////
    for J := I to N - 1 do // traiter les permutations idéales avant.
     if Mask[J] then
      for K := J + 1 to TVM.Size - 1 do
       if (B[J] = T[K]) and (B[K] = T[J]) then // Les permutations idéales.
        begin
         AddTransposition(AsTransposition(J, K));
         Swap(T, AsTransposition(J, K));
         Mask[J] := false;  // Cacher ces points
         Mask[K] := false;  // pour ne pas avoir des transpositions inutiles.
         Break
        end;
/////////////////////////////////////////////////////
    if Mask[I] then // Au cas où cette position est traité dans la boucle
                         // précédente.
     for J := I + 1 to TVM.Size - 1 do // Traiter les permutations restantes.
      if Mask[J] and (B[I] = T[J]) then
       begin
        AddTransposition(AsTransposition(I, J));
        Swap(T, AsTransposition(I, J));
        FMask[I] := false;
        Break
       end
///////////////////////////////////////////////////////
   end;

Y a t il mieux ??????

[Nemerle]

Bon, il suffit simplement de modifier "mon" algo comme suit:

quand b(i)<>t(i), on parcours tous les j>i et

- on garde le 1ier j qui vérifie b(j)=t(i) et b(j)<>t(j)
- ensuite, s'il existe un j supérieur qui vérifie les 2 conditions précédentes MAIS EN PLUS t(j)=b(i), alors c'est ce j là qu'on prend.

Le code VB où s(i,0) sont les données à modifier et s(i,1) la cible:

Code :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Dim s(100, 1) As Integer, t(100, 1) As Integer, sw As Integer, top As Integer, inc As Integer, jbest As Integer
    Dim b As Boolean
 
    i = 1
 
    While Worksheets("Feuil1").Cells(i, 4) <> ""
        s(i, 0) = Worksheets("Feuil1").Cells(i, 4)
        s(i, 1) = Worksheets("Feuil1").Cells(i, 5)
        i = i + 1
    Wend
 
    top = i
    inc = 1
    i = 1
 
    While i < top
        If s(i, 0) <> s(i, 1) Then
            j = i + 1
            b = False
            While j < top
                If s(j, 0) = s(i, 1) And s(j, 0) <> s(j, 1) Then
                    If b = True Then
                        If s(j, 1) = s(i, 0) Then
                            jbest = j
                            j = top
                        End If
                    Else
                        jbest = j
                        b = True
                    End If
                End If
                j = j + 1
            Wend
            t(inc, 0) = i
            t(inc, 1) = jbest
            sw = s(i, 0)
            s(i, 0) = s(jbest, 0)
            s(jbest, 0) = sw
            inc = inc + 1
        End If
        i = i + 1
    Wend
    For i = inc - 1 To 1 Step -1
        If i <> inc - 1 Then
            Worksheets("Feuil1").Cells(1, 7) = Worksheets("Feuil1").Cells(1, 7) & "°"
        End If
        Worksheets("Feuil1").Cells(1, 7) = Worksheets("Feuil1").Cells(1, 7) & "T(" & t(i, 0) - 1 & "," & t(i, 1) - 1 & ")"
    Next i

Résultats sur les 3 exemples:

Ex1: 3,0,4,2,3,1,4,2,1 =======> T(6,7)°T(4,7)°T(2,8)°T(1,5)°T(0,1)
0,1,1,2,2,3,3,4,4

Ex2: 4,3,0,4,3,1,1,1,2,4,3,3,2,3,4,4,1,1,3,4,2 =======> T(14,18)°T(9,20)°T(7,20)°T(6,12)°T(4,7)°T(3,17)°T(2,16)°T(1,6)°T(0,2)
0,1,1,1,1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4

Ex3: 1,1,1,3,0,4,1,2,2,2 =======> T(6,8)°T(5,9)°T(3,6)°T(0,4)
0,1,1,1,1,2,2,2,3,4


Et cela donne bien un optimum à chaque fois

[Onimaru]

Merci Nemerle,
L'algorithme marche parfaitement, voici ma transcription (en Delphi) :

Code :

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
 
 StoreSource; // Sauvegarder Source.
 JBest := 0; // Inutile, je l'ai ajoutée pour que le compilateur ne fasse pas  
             // des remarques ;).
 for I := 0 to N - 1 do
  if Source[I] <> Destination[I] then
   begin
    B := false;
    J := I + 1;
    while J <= N - 1 do
     begin
      if (Source[J] = Destination[I]) and
         (Source[J] <> Destination[J]) then
       begin
        JBest := J;
        if not B then
         B := true
        else
         if Source[I] = Destination[J] then
          J := N - 1
       end;
      Inc(J)
     end;
    J := JBest; // Pour travailler toujours avec J ;). 
    AddTransposition(AsTransposition(I, J));
    Swap(Source, AsTransposition(I, J))
   end;
 RestoreSource // Restaurer Source.

[Onimaru]

Salut à tous,
Cette solution semble marcher à merveille mais je me demande si elle est la meilleure? y a t il une optimisation à faire?
Merci.

[Nemerle]

Non, il n'y a pas d'optimisation, c'est directement un décomposition minimale (c'est le minimum à faire pour la décomposition).

[Onimaru]

Salut,
Maintenant qu'on a trouvé une permutation minimale avec sa décomposition minimale est ce qu'il est possible de retrouver les permutations et leurs décompositions minimales restantes?

[Onimaru]

Non, il n'y a pas d'optimisation, c'est directement un décomposition minimale (c'est le minimum à faire pour la décomposition).

Salut.
Je vous remercie pour l'algorithme mais je suis navré de vous décevoir :
Il ne donne pas une décomposition minimale :
L = (2,2,3,3,2,4,0,0,4,2)
L' = (0,0,2,2,2,2,3,3,4,4)

Décomposition trouvée avec votre algorithme :
(0,7)(1,6)(2,7)(3,9)(5,6)(6,9)

Autre décomposition :
(0,6)(1,7)(2,6)(3,7)(5,9)

Une différence d'une transposition.
D'après vous que faut il faire?
Merci.

[pseudocode]

Salut.
Je vous remercie pour l'algorithme mais je suis navré de vous décevoir :
Il ne donne pas une décomposition minimale :
L = (2,2,3,3,2,4,0,0,4,2)
L' = (0,0,2,2,2,2,3,3,4,4)

L'algo de Nemerle me donne bien une solution minimale

Code java :

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
int[] S = {2,2,3,3,2,4,0,0,4,2};
int[] D = {0,0,2,2,2,2,3,3,4,4};
 
int n=S.length;
for(int i=0;i<n;i++) {
	// nothing to do
	if (S[i]==D[i]) continue;
 
	int pos=-1;
	for(int j=i+1;j<n;j++) {
		// a possible swap
		if (S[j]==D[i] && S[j]!=D[j]) {
			pos=j;
			// it's an optimal swap, exit search
			if (S[j]==D[i] && S[i]==D[j]) break;
		}
	}
 
	System.out.printf("(%d,%d)",i,pos);
	int tmp=S[pos]; S[pos]=S[i]; S[i]=tmp;
}

--> (0,7)(1,6)(2,6)(3,7)(5,9)

[Nemerle]

Et toc. quand on sait pas coder, on reste à la maison. Merci pseudocode

[Onimaru]

Et toc. quand on sait pas coder, on reste à la maison. Merci pseudocode

Salut, je suis à la maison non parce que je ne sais pas coder, mais parce qu'il pleut dehors.

En ce qui me concerne j'ai traduit exactement votre algo en Pascal, ni plus ni moins. L'algo écrit par Pseudocode est autre transcription.

Le principe des deux est le même et c'est le votre et je suis conscient de ça sauf que : votre transcription ne le respecte pas et celle de Pseudocode le respecte.

Si j'ai fait erreur dites le moi

[Onimaru]

L'algo de Nemerle me donne bien une solution minimale

Code java :

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
int[] S = {2,2,3,3,2,4,0,0,4,2};
int[] D = {0,0,2,2,2,2,3,3,4,4};
 
int n=S.length;
for(int i=0;i<n;i++) {
	// nothing to do
	if (S[i]==D[i]) continue;
 
	int pos=-1;
	for(int j=i+1;j<n;j++) {
		// a possible swap
		if (S[j]==D[i] && S[j]!=D[j]) {
			pos=j;
			// it's an optimal swap, exit search
			if (S[j]==D[i] && S[i]==D[j]) break;
		}
	}
 
	System.out.printf("(%d,%d)",i,pos);
	int tmp=S[pos]; S[pos]=S[i]; S[i]=tmp;
}

--> (0,7)(1,6)(2,6)(3,7)(5,9)

Merci pour l'algorithme