Mesure de désordre

Posté par cepamoi cepamoi

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.

Posté par Surb Surb

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.

Posté par cepamoi cepamoi

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...

Posté par verdurin verdurin

Bonjour, voici un lien trouvé en cherchant "permutations distance"


j'espère qu'il te sera utile

Posté par cepamoi cepamoi

Bonjour,

Merci beaucoup, verdurin. C'est exactement ce que je cherchais.

En fait, j'avais déjà implémenté la "deviation distance" (cf. mon post précédent). Elle donne des résultats moyens pour mon problème. Je vais essayer d'autres distances de l'article.

Merci encore.