Tri des permutations par inversion

Bonjour Sana,
Non, l'indice de k dans p2 ne peut pas être i : "pour trouver le premier élément k!=i". Effectivement k=i va marcher, mais il faut ignorer ce cas.

Le cas qui peut arriver c'est que k n'existe pas, auquel cas p3=(p(i)...p(n)) et p4 n'existe pas. Ta permutation finale sera donc la concaténation des permutations p1 p6.

Cordialement

Mais vous ne m'avez pas compris:
k peut être le premier élément de p2 donc p3 sera inexistante car on n' a pas l'élément k-1.
Si vous appliquer l'algorithme sur cette permutation 1 2 3 5 7 4 6 8 9 vous allez comprendre ce que j viens de dire.
Merci.
Cordialement.

Bonsoir Sana,
Non, je pense que c'est toi qui m'as mal compris. Il y avait bien une erreur, mais je ne pense pas qu'elle se situait ici. Je t'écris ici un nouvel algorithme proprement :
- L'algorithme que l'on va écrire permet de trouver la permutation triée de la permutation donnée en entrée. Par exemple, le résultat de l'algorithme pour (1245736) sera (1234567) et celui de (432) sera (234).
- Soit I(p) l'inversion d'une permutation (I((1234)) = (4321) par exemple)
- Soit n le nombre d'éléments de la permutation (pour p=(1234), n = 4)
- Soit A(p, d) l'algorithme que l'on est en train d'écrire (c'est important car on va l'appeler récursivement). p est la permutation que l'on souhaite trier, et d est la valeur minimale moins 1 contenue dans la permutation. Par défaut (pour résoudre ton exercice), on va appeler A(p, 0) car ta permutation commence à 1.

- On effectue le test p(i) égal i+n (comme le début de ton algorithme). Dès que p(i+n) != i, alors on découpe la permutation p en p1 et p2. p1=(p(1) p(2) ... p(i-1)), donc est la permutation identité à l'ordre i-1. p2=(p(i)...p(n)).
Si on ne trouve aucun i correspondant, alors on retourne p.
- Soit p3 = A(p2, i). Si notre algorithme est correct, alors p3 est un sous-ensemble de la permutation identité (ie p3 est trié).
- On effectue alors la manipulation p = p1 I(p2(i) I(p3)). On retourne p

Je pense que cet algorithme là est correct. Quant à savoir s'il est optimal, ça je ne sais pas te le prouver.
Cordialement,

Bonjour Marco,
J'ai pas compris pourquoi tu compares p(i+n) avec i, en principe on doit comparer p(i) avec i.
Si on applique ton algorithme sur (1 2 3 5 7 4 6 8 9) donc d'après ce que j'ai compris p1=(1 2 3) et p2=(5 7 4 6 8 9), maintenant comment trouver p3 ( car dans p2 on va comparer 5 avec 1 (car i=1))?
Merci de me répondre.
Cordialement.

Bonjour Sana,
En fait, j'ai encore fait une erreur : je ne veux pas comparer p(i+n) avec i mais p(i) avec i+d.
C'est justement pour pouvoir trier les permutations qui ne commencent pas à 1 (comme p=(354) par exemple; ici je veux savoir si p(1) = 3).

Pour reprendre ton exemple, on va comparer 5 avec la valeur minimale de la permutation : 4. Comme c'est différent, je vais découper (574689) en 2 : (5) et (74689)...

Cordialement,

Bonsoir Marco,
Merci bien pour votre réponse mais est-ce que vous pouvez appliquer tout votre algorithme sur l'exemple que je vous ai donné pour mieux comprendre? Merci.
Cordialement.

Bonsoir Sana,
Tu as raison, on peut utiliser p(i) != i. Cependant, en utilisant p(i) > i, ça suffit car on va trier la liste petit à petit, comme tu vas le voir sur l'exemple qui suit (si p(i) > i, alors cela implique p(i) != i).
En gros, initialement, p(i) >= i (vu que i=1). Et si p(i) >i, on va le mettre à la position p(i), donc notre condition sera respectée.

Il y a encore une erreur dans mettre :

fonction mettre(permutation p, element e) : permutation
entier n = taille(p)
entier i = p(e) //nouvelle position de e dans la permutation
permutation p1 = (p(0), ..., p(e-1))
permutation p2 = (p(e))
permutation p3 = (p(e+1), ..., p(i-1))
permutation p4 = (p(i) ... p(n))
retourner p1 I(p2 I(p3)) p4 //I est l'inversion telle que tu l'as définie

Si p(e-1) n'existe pas, p1 n'existe pas et on retourne I(p2 I(p3)) p4.
Ce n'est pas p1 I(p2) I(p3) mais p1 I(p2 I(p3)). C'est la double inversion telle que tu l'as définie dans l'énoncé :
12374568 : p1 = 123; p2=7; p3=456; p4=8
I(p3) = 654; p2 I(p3) = 7654; I(p2 I(p3)) = 4567
Enfin, p1 I(p2 I(p3)) p4 = 12345678

Maintenant sur ton exemple :

p=(1 2 3 5 7 4 6 8 9)
En i=4, p(i)=5 donc p(i) > i, donc on appelle mettre :
 p1=123
 p2=5
 p3=7
 p4=4689
p=(123754689)

En i=4, p(i)=7 donc p(i) > i, donc on appelle mettre :
 p1=123
 p2=7
 p3=54
 p4 = 689
p=(123547689)

En i=4, p(i)=5 donc p(i) > i donc on appelle mettre :
 p1=123
 p2=5
 p3=4
 p4=7689
p=(123457689)

En i=6, p(i)=7 donc p(i)>i donc on appelle mettre :
 p1=12345
 p2=7
 p3=6
 p4=89
p=(123456789)

cqfd

Cordialement,

Bonjour Marco,
Merci d'avoir voulu m'aider.
J'ai quelques remarques à vous dire concernant la fonction mettre:
I(p2 I(p(3))) = P(3) I(P(2)) = P(3) P(2) (car p2 contient toujours un seul élément) donc ici je ne vois pas l'utilité de l'inversion?! Or moi il faut que je travaille avec les inversions et le problème c'est de trouver le nombre minimum d'inversions pour obtenir la permutation identité.
Est-ce-que vous pouvez me donner une idée sur comment écrire tout un algorithme qui à partir de la permutation initiale génère toutes les inversions possibles permettant de la trier? il faut implémenter un arbre non?
Merci,
cordialement,

Bonsoir Sana,
Effectivement, je pense que le fait d'utiliser des inversions est moins efficace que de ne pas en utiliser.
L'avantage des permutations, c'est que ça permet de déplacer plusieurs éléments en même temps (avantage qu'on n'utilise pas du tout dans mon algorithme).

Donc effectivement, pour utiliser les permutations au mieux, il faudrait que dès que p(i) > i, on crée p2 tel que quelque soit j, p2(j+1) = p2(j) +1 (on déplace non plus un seul élément, mais la suite d'éléments).

En faisant cela, on diminue le nombre d'inversions, mais je ne pense pas qu'on atteigne le nombre minimal.

Pour ta demande d'algorithme, je n'en ai aucune idée.

Cordialement,