Discussion :

[pseudocode]

L'algo donne une des solutions optimales.

Si on calcule le nombre d'échange effectué en fonction des cycles présents dans la permutation :
- Pour les cycles de longueur 1, il fait 0 échange.
- Pour les cycles de longueur 2, il fait 1 échange.
- Pour les cycles de longueur k, il fait k-1 échanges. (*)

(*) car un échange transforme un cycle de longueur k en cycle de longueur k-1.

Si on pose N la taille de la permutation, et P le nombre d'échange effectué, alors :

N = 1*NbCycle1 + 2*NbCycle2 + 3*NbCycle3 + ... + N*NbCycleN
P = 0*NbCycle1 + 1*NbCycle2 + 2*NbCycle3 + ... + (N-1)*NbCycleN

avec NbCyclek = le nombre de cycle de taille k présent dans la permutation.

De là, on trouve

N-P = NbCycle1 + NbCycle2 + NbCycle3 + ... + NbCycleN

c'et à dire

P = N - le nombre de cycles dans N

C'est à dire le décrément de la permutation, qui se trouve être le nombre minimum de transposition.

[Onimaru]

Merci pour l'explication.

[Onimaru]

Salut à tous,
Navré de vous décevoir :
L = (3,2,4,2,2,2,9,15,0,4,0,1)
L' = (0,0,1,2,2,2,2,3,4,4,9,15)

Résultat trouvé avec l'algorithme de Nemerle-Pseudocode :
(0,10)(1,8)(2,11)(6,8)(7,10)(8,11)(10,11)

Le résultat que j'ai trouvé :
(1,10)(10,6)|(0,3)(3,2)(2,11)(11,7)

Deux cycles disjoints : (1,10,6) et (0,8,2,11,7).

[pseudocode]

Salut à tous,
Navré de vous décevoir :
L = (3,2,4,2,2,2,9,15,0,4,0,1)
L' = (0,0,1,2,2,2,2,3,4,4,9,15)

Résultat trouvé avec l'algorithme de Nemerle-Pseudocode :
(0,10)(1,8)(2,11)(6,8)(7,10)(8,11)(10,11)

Le résultat que j'ai trouvé :
(1,10)(10,6)|(0,3)(3,2)(2,11)(11,7)

Deux cycles disjoints : (1,10,6) et (0,8,2,11,7).

Ah, exact. Avec les doublons l'algo n'échange pas forcément deux éléments qui sont dans le même cycle. Il faut réordonner les ensembles par cycle pour que cela fonctionne, ou alors modifier l'algo pour qu'il fasse des échanges seulement dans le meme cycle.

[pseudocode]

exemple de code, en marquant les supports des cycles (pas très optimisé)

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
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
int[] S = {3,2,4,2,2,2,9,15,0,4,0, 1};
int[] D = {0,0,1,2,2,2,2, 3,4,4,9,15};
 
int n=S.length;
 
// mark disjoint supports  
int[] support = new int[n];
int cnt=0;
for(int i=0;i<n;i++) {
	// find first non marked element
	if (support[i]!=0) continue;
	cnt++;
 
	// mark the support for the element
	support[i]=cnt;
	int next = D[i];
	// jump to next element, until it loops
	while(next!=S[i]) {
		int k=-1;
		for(int j=0;j<n;j++)
			if (support[j]==0 && S[j]!=D[j] && S[j]==next) {
				k = j;
				if (D[j]==S[i])	break;
			}
		support[k]=cnt;
		next=D[k];
	}
}
 
 
// now performs the permutation
for(int i=0;i<n;i++) {
	// nothing to do
	if (S[i]==D[i]) continue;
 
	// find the first possible swap in the same support
	int pos=-1;
	for(int j=i+1;j<n;j++) {
		if (S[j]==D[i] && support[i]==support[j]) {
			pos=j;
			break;
		}
	}
 
	// do the swap
	System.out.printf("(%d,%d)",i,pos);
	int tmp=S[pos]; S[pos]=S[i]; S[i]=tmp;
}

Cela dit ca serait mieux s'il n'y avait pas de doublons dans la liste, ou alors si on travaillait directement sur des cycles disjoints.

[Onimaru]

Merci encore une fois

[Onimaru]

Salut à tous,
J'ai enfin trouvé la solution :
-Considérer la permutation comme un graphe (les nœuds sont les éléments et les transpositions sont les arcs).
-Trouver tout les cycles de ce graphe.
-Trier les cycles selon la longueur pour privilégier les cycles les plus courts.
-Pour chaque cycle on cherche les positions qui lui conviennent.
-Extraire les permutations depuis le plus court cycle jusqu'au plus long en évitant les cycles qui contiennent des positions déjà utilisées.