Inscription / Connexion Nouveau Sujet
Mesure de désordre
Bonjour,
On a une première liste d'éléments, tous différents, triés dans un ordre donné, par exemple {A,B,C,D}. On a une seconde liste contenant exactement les mêmes éléments, mais triés dans un ordre différent, par exemple {C,A,D,B}.
Je voudrais construire une mesure de distance entre les deux listes, ou, en d'autres termes, mesurer le désordre de la seconde liste par rapport à la première : plus l'ordre de la seconde liste sera différent de celui de la première, plus la distance sera grande.
J'imagine qu'il existe différents algorithmes "standards" pour mesurer cela, mais je ne sais pas où chercher.
Merci d'avance.
Bonjour,
J'imagine qu'il doit être possible de construire une metrique définie par le nombre minimum de permutations qu'il faut utiliser pour passer d'une liste à l'autre. Mais c'est pas sure que ca marche et que ce soit la plus simple.
Effectivement, on peut imaginer diverses métriques, et notamment avec le nombre minimum de permutations.
J'avais aussi imaginé de construire une mesure à partir de la valeur absolue de la différence des positions de chaque élément dans les deux listes.
Mais en fait, je me disais que ce problème était certainement un problème assez classique, et que donc de bonnes solutions avaient été trouvées. Il serait sans doute plus judicieux d'utiliser une de ces solutions classiques, plutôt que de bricoler quelque chose tout seul dans mon coin...
Annuler
connectez vous