CommentCaMarche
Recherche
Posez votre question Signaler

Tri des permutations par inversion

Sana - Dernière réponse le 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
Lire la suite 
Réponse
+0
moins plus
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,
Sana- 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.
Répondre
Marco la baraque 998Messages postés vendredi 9 mai 2008Date d'inscription ContributeurStatut 5 novembre 2009Dernière intervention - 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,
Répondre
Sana- 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.
Répondre
Marco la baraque 998Messages postés vendredi 9 mai 2008Date d'inscription ContributeurStatut 5 novembre 2009Dernière intervention - 14 nov. 2008 à 15:11
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,
Répondre
Sana- 14 nov. 2008 à 17:16
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.
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
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+

Ajouter un commentaire
Réponse
+0
moins plus
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 ?
sana- 16 nov. 2008 à 22:23
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,
Répondre
Marco la baraque 998Messages postés vendredi 9 mai 2008Date d'inscription ContributeurStatut 5 novembre 2009Dernière intervention - 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,
Répondre
sana- 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,
Répondre
Marco la baraque 998Messages postés vendredi 9 mai 2008Date d'inscription ContributeurStatut 5 novembre 2009Dernière intervention - 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,
Répondre
Ajouter un commentaire
Ce document intitulé «  tri des permutations par inversion  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.