Existe-t-il un moyen de mesurer le degré de tri d'une liste?

Question

Est-il est un moyen de mesurer comment trié la liste?

Je veux dire, il n'est pas question de savoir si une liste est triée ou non (boolean), mais quelque chose comme un rapport de la "sortness", quelque chose comme le coefficient de corrélation statistique.

Par exemple,

• Si les éléments d'une liste sont dans l'ordre croissant, puis son taux serait de 1,0

• Si la liste est triée en ordre décroissant, son taux serait de -1.0

• Si la liste est presque classés dans l'ordre croissant, son taux serait de 0,9 ou une valeur proche de 1.

• Si la liste n'est pas triée à tous (aléatoire), son taux serait proche de 0

Je vais écrire une petite bibliothèque en Scala pour la pratique. Je pense qu'un tri des taux serait utile, mais je n'ai pas trouver toutes les informations à propos de quelque chose comme ça. Peut-être que je ne sais pas suffisant conditions pour le concept.

Answer 1

Vous pouvez simplement compter le nombre d'inversions dans la liste.

Inversion

Une inversion dans une séquence d'éléments de type T est une paire d'éléments de la séquence qui apparaissent hors de l'ordre, selon certains de la commande < sur l'ensemble de l' T'.

De Wikipedia:

Officiellement, laissez - A(1), A(2), ..., A(n) être une séquence de n numéros.
Si i < j et A(i) > A(j), puis la paire (i,j) s'appelle une inversion de A.

L' inversion de numéro de séquence est une mesure commune de son sortedness.
Officiellement, l'inversion nombre est le nombre d'inversions, qui est,

Pour faire ces définitions plus clair, prenons l'exemple de la séquence de 9, 5, 7, 6. Cette séquence a les inversions (0,1), (0,2), (0,3), (2,3) et l' inversion nombre 4.

Si vous voulez une valeur comprise entre 0 et 1, vous pouvez diviser l'inversion nombre en N choose 2.

Pour créer un algorithme pour le calcul de ce score pour comment triés une liste, vous avez deux approches:

Approche 1 (Déterministe)

Modifier votre favori algorithme de tri pour garder une trace de la façon dont de nombreuses inversions c'est la correction, car il fonctionne. Si ce n'est pas négligeable et a différentes implémentations en fonction de l'algorithme de tri que vous choisissez, vous allez vous retrouver avec un algorithme qui n'est pas plus coûteuse (en termes de complexité) que l'algorithme de tri que vous avez commencé avec.

Si vous prenez cette route, sachez que ce n'est pas aussi simple que de compter "swaps." Mergesort, par exemple, est le pire des cas O(N log N), mais s'il est exécuté sur une liste triée dans l'ordre décroissant, il va corriger tous N choose 2 des inversions. C'est O(N^2) inversions corrigé en O(N log N) des opérations. De sorte que certaines opérations doivent inévitablement être la correction de plus d'une inversion à la fois. Vous devez être prudent avec votre mise en œuvre. Remarque: vous pouvez le faire avec O(N log N) de la complexité, c'est difficile.

Liés: le calcul du nombre de "inversions" dans une permutation

Approche 2 (Stochastique)

• Au hasard de l'échantillon paires (i,j)où i != j
• Pour chaque paire, de déterminer si l' list[min(i,j)] < list[max(i,j)] (0 ou 1)
• Calculer la moyenne de ces comparaisons, et puis normaliser en N choose 2

---

Personnellement, je ne aller avec l'approche stochastique, sauf si vous avez une exigence d'exactitude - si seulement parce qu'il est si facile à mettre en œuvre.

---

Si ce que vous voulez vraiment est une valeur (z') entre -1 (tri décroissant) 1 (classés dans l'ordre croissant), vous pouvez tout simplement la carte de la valeur au-dessus de (z), qui est entre 0 (classés dans l'ordre croissant) et 1 (tri décroissant), à cette plage à l'aide de cette formule:

z' = -2 * z + 1

Answer 2

La mesure traditionnelle du classement d'une liste (ou d'une autre structure séquentielle) est le nombre d'inversions.

Le nombre d'inversions est le nombre de couples (a, b) st indices de a <b ET b << a. À ces fins, << représente la relation d'ordre que vous choisissez pour votre type particulier.

Une liste entièrement triée n'a pas d'inversions, et une liste complètement inversée a le nombre maximum d'inversions.

Answer 3

Vous pouvez utiliser la corrélation réelle.

Supposons que pour chaque élément de la liste triée, vous affectez un rang entier à partir de zéro. Notez qu'un graphique de l'indice de position des éléments par rapport au rang ressemblera à des points dans une ligne droite (corrélation de 1,0 entre la position et le rang).

Vous pouvez calculer une corrélation sur ces données. Pour un tri inverse, vous obtiendrez -1 et ainsi de suite.

Answer 4

Il y a eu beaucoup de réponses, et je voudrais ajouter un aspect mathématique de l'exhaustivité:

• Vous pouvez mesurer la triés une liste est en mesure combien il est corrélé à une liste triée. Pour ce faire, vous pouvez utiliser le grade de corrélation (la plus connue étant de Spearman est), qui est exactement le même que l'habitude de corrélation, mais il utilise le rang d'éléments dans une liste au lieu de les valeurs analogiques de ses éléments.

• De nombreuses extensions existent, comme une corrélation coefficient (+1 pour connaître les trier, -1 pour l'exacte inversion)

• Cela vous permet d'avoir des propriétés statistiques de cette mesure, comme le permutational théorème de la limite centrale, qui permet de connaître la répartition de cette mesure pour des listes aléatoires.

Answer 5

En dehors du comptage d'inversion, pour les listes numériques, la distance carrée moyenne de l'état trié est imaginable:

 #! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case