Je pense que l'énoncé de ma question n'est pas du tout clair. :)
Si par exemple, je veux classer par ordre croissant (2 3 1)
Il faut que je fasse au minimum deux permutations
(2 3 1) -> (2 1 3) -> (1 2 3)
Mais existe t-il un algorithme pour de plus grandes listes?
Par exemple ( 2 4 1 3 7 6 8 5 9) ou autres?
2007-06-29 00:42:19 · 8 réponses · demandé par -O- 7 dans Sciences et mathématiques ➔ Mathématiques
Il y a un problème de vocabulaire: ce que tu appelles permutation s'appelle transposition...
Cette recherche du minimum me parait difficile...
Je pense qu'il doit s'agir probablement d'un problème NP...
(car il est sans doute obligatoire de balayer une bonne partie des possibilités pour justifier que l'on a le minimum)
Par contre 2 choses sont faciles à obtenir:
1) ce minimun est majoré par le nombre d'objets mal placé au départ (car chaque transposition peut faire baisser ce nombre d'un ou plus) et minoré par le nombre d'objet mal placé divisé par 2 (car chaque transposition peut faire baisser ce nombre de 2 au plus)
2) la parité de ce nombre est connu (cela correspond à la signature de la permutation
Si tu veux simplement un algorithme efficace pour remettre de l'ordre, il en existe de rapides (coût O(n*ln( n)) )
2007-06-29 02:05:09 · answer #1 · answered by Anonymous · 2⤊ 0⤋
Donald Knuth etait un specialiste des algoritmes de tri:
http://fr.search.yahoo.com/search?search=knuth&ei=UTF-8&fr=ks-ans&ico-yahoo-search-value=http%3A%2F%2Frds.yahoo.com%2F_ylt%3DAnxjYm6XMvAwRbvi94WlR6orAgx.%2FSIG%3D11lgg7uud%2FEXP%3D1183480586%2F*-http%253A%2F%2Ffr.search.yahoo.com%2Fsearch&ico-wikipedia-search-value=http%3A%2F%2Frds.yahoo.com%2F_ylt%3DAoUc9HvJEyekxOoIYzlNe.IrAgx.%2FSIG%3D1215og61s%2FEXP%3D1183480586%2F*-http%253A%2F%2Ffr.wikipedia.org%2Fwiki%2FSpecial%253aSearch&p=knuth
2007-07-02 12:38:40 · answer #2 · answered by Louis XV 7 · 0⤊ 0⤋
Par "permutations",tu entends "transpositions"?
La première chose c'est de placer 1 en premier,ce qui requiert au plus n-1 transpositions.
Ensuite 2 en second:n-2
Enfin n-1 en (n-1)ème place:1
Finalement,le nombre de transpositions ne dépassera pas 1+2+...+n-1=n(n-1)/2.
Sinon une permutation (au vrai sens du terme) suffit,puisqu'une permutation,par définition,c'est une bijection de {1,2,3,...,n-1,n} dans lui-même.
En fait je t'ai donné un maximum,mais comme minimum,ça peut être 0 si l'ordre est déjà formé!
2007-06-30 10:51:23 · answer #3 · answered by Anonymous · 0⤊ 0⤋
on peut classer une liste quelconque de n éléments en faisant n-1 permutations
puisque pour chacune des positions, il suffit de rechercher la valeur dans celles qui restent à trier
(la permutation de l'avant dernière position positionnant forcément la dernière position)
mais le nombre minimum dépend de l'état de la liste au départ de l'opération (puisque si elle est déjà partiellement triée, il y en a moins à faire)
2007-06-30 07:53:38 · answer #4 · answered by jam63112 6 · 0⤊ 0⤋
Sachant que la liste est mélangée, il y a au moins 1 élément mal ordonné (et par conséquent un second).
Pour obtenir le nombre minimum d'actions nécessaires au rangement, il faut chercher le nombre entier le plus petit, strictement supérieur à zéro (soit 1).
En clair : le minimum est 1 = une unique inversion pour arriver à une liste triée !
Pour le maximum, une infinité : il suffit de se débrouiller pour faire des actions qui ne trient pas la liste :/ sauf la dernière (après une infinité, ca fait long).
Pour le minimum le plus grand, il faut compter... (note: j'admets que le fait d'ordonner le tri ne modifie pas le nombre d'actions total pour obtenir une liste triée).
Pour une liste de N éléments, l'élément le plus éloigné de sa position originale requiert N-1 actions (il faut le ramener de la position N à la position 1).
Une fois le premier élément positionné, il faut positionner le second; ce qui revient à trier le premier élément d'une liste de longueur N-1.
Exemple : liste {4,3,2,1} avec 4 éléments
Après 3 (=4-1) actions => {3,2,1,4}
Le 4 est bien positionné, il reste 3 éléments à ranger.
Après 2 (=3-1) actions => {2,1,3,4}
3 et 4 sont bien positionnés, il reste 2 élements à ranger.
Et ainsi de suite => etc => {1,2,3,4}
Soit une jolie suite avec :
Nombre d'actions pour une liste à N éléments = somme des entiers de 1 à N-1.
2007-06-29 18:56:27 · answer #5 · answered by Avataration 2 · 1⤊ 1⤋
Tout ce qu'on peut te donner c'est un nombre MAXIMUM (et non MINIMUM) de combinaisons possibles.
En l'occurence pour N nombres on a Factoriel(N) possibilité (s'écrit aussi : N! )
N! = N x (N-1) x (N-2) x (N-3) x ............ x 2 x 1
2! = 2 x 1 = 2
3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
Tu aurais pu aussi bien prendre (B C A) -> (B A C) -> (A B C)
Le fait de prendre des chiffres n'est qu'une autre réprésentation symbolique mais n'interviens pas dans le calcul.
2007-06-29 10:00:30 · answer #6 · answered by Article 35 Droits De L Homme 6 · 1⤊ 1⤋
Une banane pour celui qui trouve.
Il faut d'abord connaitre tous les algorythmes de classement avant de pouvoir comparer.
Parce qu'il existe peut être qq part un algo top génial auquel personne n'a pensé. En tout cas personne ne pourra me prouver le contraire.
Je pense que c'est impossible.
Celui (ou celle) qui m'a mis un pouce en bas est prié de prouver que j'ai tort !
2007-06-29 09:55:44 · answer #7 · answered by Anonymous · 1⤊ 1⤋
A mon avis ce qui serait le plus performant serait de proceder au tri de ta liste et de compter le nombre d'iterations de ton algo
2007-06-29 07:59:05 · answer #8 · answered by godshifter 2 · 1⤊ 1⤋