Tri des permutations par inversion

Fermé
Sana - 12 nov. 2008 à 12:03
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 - 17 nov. 2008 à 19:57
Bonjour,
j'ai un problème à résoudre. Le problème s'intitule "tri par inversion" (sorting by reversal) et qui se présente comme suit: étant donnée une permutation quelconque (par exemple 3 1 2 4), on désire transformer cette permutation en l'identité (1 2 3 4) en un nombre minimum d'étapes et en utilisant l'inversion (par exemple l'inversion de 3 1 2 4 est 4 2 1 3). Une manière de se faire est de comparer l'élément p(i) de la permutation p avec l'indice i de sa position, s'ils sont égaux on passe à l'émément suivant sinon on applique une inversion entre i et la position de p(i). L'idée de cet algorithme s'inspire du faite que dans la permutation identité chaque élément est égal à l'indice de sa position. Mais cet algorithme ne garantie pas le plus petit nombre d'inversion vu que si on l'applique sur cette permutation (6 1 2 3 4 5) on obtiendra 5 inversions donc 5 étapes alors que cette permutation peut être triée en 2 étapes sulement: (6 1 2 3 4 5) -> (5 4 3 2 1 6) -> (1 2 3 4 5 6).
Je serai vraiment reconnaissante si vous m'aidez à résoudre ce problème.
Merci

3 réponses

Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329
12 nov. 2008 à 20:21
Bonsoir Sana,
Que penses-tu de l'algorithme suivant :
- 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
- On effectue le test p(i) égal i (comme le début de ton algorithme). Dès que p(i) != 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)).
- On parcours p2 pour trouver le premier élément k!=i tel que p3(p(k)) != k. Soit p3=(p2(i)...p2(k-1)) et p4=(p2(k)...p2(n-i)).
-On créer p5=I(p3), qu'on inverse en partie (comme dans ton exemple). C'est-à-dire qu'on inverse tous les éléments sauf le dernier. Appelons p6 cette permutation.
- On crée la permutation P en concaténant les permutations p1, p6, p4
- On recommence l'opération sur P à partir de i

J'espère que c'est assez clair...

Cordialement,
0
Bonjour,
Merci bien pour votre réponse. Mais j'ai quelques remarques à vous dire: Les 4 dernières étapes ne sont pas assez claires. En effet, dans la quatrième étape, si l'indice de k dans p2 est 1 (donc i=1) alors on aura p4=p2 et p3 sera inexistante! Vous pouvez appliquer votre algorithme sur la permutation suivante (1 2 3 5 7 4 6 8 9).
C'est une bonne idée mais à rectifier! D'après mes recherches, j'ai trouvé aussi qu'il est possible d'utiliser la notion de point de rupture (breakpoint): deux éléments de la permutation qui ne sont pas consécutifs constituent un point de rupture (exemple: (3 5) est un point de rupture). Si vous remarquez, dans la permutation identité il n'y aucun point de rupture donc le problème se ramène à minimiser le nombre de points de rupture jusqu'à obtenir la permutaion identité ( donc zéro point de rupture car dans la permutation dentité tous les éléments sont consécutifs). C'est une autre idée mais il reste à voir comment faire un algorithme qui minimise le nombre de points de rupture et en utilisant aussi l'inversion.
Merci bien.
Cordialement.
0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329 > Sana
13 nov. 2008 à 10:52
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
0
Sana > Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009
13 nov. 2008 à 11:41
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.
0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329 > Sana
13 nov. 2008 à 21:33
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,
0
Sana > Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009
14 nov. 2008 à 09:45
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.
0
lermite222 Messages postés 8724 Date d'inscription dimanche 8 avril 2007 Statut Contributeur Dernière intervention 22 janvier 2020 1 190
13 nov. 2008 à 11:55
Bonjour,
Je pense que dans ta démo tu a fait une erreur.
étapes sulement: (6 1 2 3 4 5) -> (5 4 3 2 1 6) -> (1 2 3 4 5 6).
probablement
étapes sulement: (6 1 2 3 4 5) -> (5 1 2 3 4 6) -> (1 2 3 4 5 6).

parcourir P() jusqu'à trouver une valeur supérieure, si on arrive à la fin de P() et qu'ont a pas trouver, reculer toute les valeur de 1 vers la gauche et mettre P(1) en P(Fin)
Si le principe de chercher le moins de permutations possibles est la condition indiquée c'est une solution, mais le nombre de test serra beaucoup plus élever qu'avec un tri normal.
A+

0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329
14 nov. 2008 à 22:33
Bonsoir Sana,
J'écris en bas parce qu'à force on n'a plus de place là haut.
Ma solution était encore fausse (elle ne fonctionnait pas avec ton exemple).

J'ai trouvé une solution assez facile qui est optimale pour ton exemple, et pas mal dans la plupart des cas.
fonction identite(permutation p) : permutation
entier i = 1
entier n = taille(p)
tant i <= n faire
 si p(i) > i
  p = mettre(p, p(i))
 sinon
  i = i + 1
fin tant que
retourner p

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


Cet algorithme fonctionne sur ton exemple. En clair : tant qu'un élément n'est pas à sa place, on le déplace à sa place.
Sur (612345) la permutation se fait en une passe. Par contre, dans certains cas il est nul : (234561) se fait en O(n^n)...

La solution optimale, à mon avis, c'est une variation de cet algorithme : au lieu de positionner chaque élément à sa place (quitte à le redéplacer plus tard), on déplace uniquement les éléments qui ne bougeront jamais.
Par exemple sur (126435), on peut déplacer 6 car la taille de p est 6 (donc p ne sera jamais décallé vers la gauche). Puis comme 4 c'est ni la suite de 12, ni l'élément précédent 6, on le laisse.
Ensuite, on s'occupe de 3. 3 est la suite de 12 donc on le déplace. Puis 5 est bien placé (avant 6) donc on n'y touche pas.
Ensuite on refait une passe en commençant à partir du premier élément qu'on n'a pas déplacé (ici 4).

Qu'en penses-tu ?
0
Bonsoir,
je ne vois pas pourquoi vous testez p(i)>i (or on a besoin d'avoir p(i)=i et non pas p(i)>i).
Secondo, dans la foction mettre, on peut tomber sur le cas où p(e-1) n'existe pas et ceci dans le cas où e=p(1)?
Je ne comprend pas aussi pourquoi la valeur de retour de la fonction mettre est p1 I(p2) I(p3)?
Je serai reconaissante si vous appliquez votre algorithme sur l'exemple que je vous ai donné.
Merci.
Cordialement,
0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329 > sana
16 nov. 2008 à 22:53
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,
0
sana > Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009
17 nov. 2008 à 11:44
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,
0
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 329 > sana
17 nov. 2008 à 19:57
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,
0