¿Hay alguna manera de medir qué tan ordenada está una lista?

Quiero decir, no se trata de saber si una lista está ordenada o no (booleana), sino algo así como una relación de "clasificación", algo así como el coeficiente de correlación en las estadísticas.

Por ejemplo,

• Si los elementos de una lista están en orden ascendente, su tasa sería 1.0

• Si la lista se ordena descendente, su tasa sería -1.0

• Si la lista está casi ordenada ascendente, su tasa sería 0.9 o algún valor cercano a 1.

• Si la lista no está ordenada (aleatoria), su tasa sería cercana a 0

Estoy escribiendo una pequeña biblioteca en Scala para practicar. Creo que una tasa de clasificación sería útil, pero no encuentro ninguna información sobre algo así. Tal vez no conozco los términos adecuados para el concepto.

Simplemente puede contar el número de inversiones en la lista.

Inversión

Una inversión en una secuencia de elementos de tipo Tes un par de elementos de secuencia que aparecen fuera de orden de acuerdo con algún orden <en el conjunto de T's.

De Wikipedia :

Formalmente, seamos A(1), A(2), ..., A(n)una secuencia de nnúmeros.
Si i < jy A(i) > A(j), entonces el par (i,j)se llama inversión de A.

El número de inversión de una secuencia es una medida común de su clasificación.
Formalmente, el número de inversión se define como el número de inversiones, es decir,

Para aclarar estas definiciones, considere la secuencia de ejemplo 9, 5, 7, 6. Esta secuencia tiene las inversiones (0,1), (0,2), (0,3), (2,3) y el número de inversión 4 .

Si desea un valor entre 0y 1, puede dividir el número de inversión entre N choose 2.

Para crear realmente un algoritmo para calcular este puntaje según la clasificación de una lista, tiene dos enfoques:

Enfoque 1 (determinista)

Modifique su algoritmo de clasificación favorito para realizar un seguimiento de cuántas inversiones está corrigiendo mientras se ejecuta. Aunque esto no es trivial y tiene implementaciones diferentes según el algoritmo de clasificación que elija, terminará con un algoritmo que no es más costoso (en términos de complejidad) que el algoritmo de clasificación con el que comenzó.

Si toma esta ruta, tenga en cuenta que no es tan simple como contar "intercambios". Mergesort, por ejemplo, es el peor de los casos O(N log N), pero si se ejecuta en una lista ordenada en orden descendente, corregirá todas las N choose 2inversiones. Eso es O(N^2)inversiones corregidas en las O(N log N)operaciones. Por lo tanto, algunas operaciones inevitablemente deben corregir más de una inversión a la vez. Tienes que tener cuidado con tu implementación. Nota: puedes hacer esto con O(N log N)complejidad, es complicado.

Relacionado: calcular el número de "inversiones" en una permutación

Enfoque 2 (estocástico)

• Muestra aleatoria de pares (i,j), dondei != j
• Para cada par, determine si list[min(i,j)] < list[max(i,j)](0 o 1)
• Calcule el promedio de estas comparaciones y luego normalice por N choose 2

Yo personalmente seguiría el enfoque estocástico a menos que tenga un requisito de exactitud, aunque solo sea porque es muy fácil de implementar.

Si lo que realmente quiere es un valor ( z') entre -1(ordenado descendente) a 1(ordenado ascendente), simplemente puede asignar el valor anterior ( z), que está entre 0(ordenado ascendente) y 1(ordenado descendente), a este rango utilizando esta fórmula :

z' = -2 * z + 1

La medida tradicional de cuán ordenada es una lista (u otra estructura secuencial) es el número de inversiones.

El número de inversiones es el número de pares (a, b) st index de a <b AND b <<a. Para estos fines, <<representa cualquier relación de orden que elija para su tipo particular.

Una lista completamente ordenada no tiene inversiones, y una lista completamente invertida tiene el número máximo de inversiones.

Puedes usar la correlación real.

Suponga que a cada elemento de la lista ordenada, le asigna un rango entero a partir de cero. Tenga en cuenta que un gráfico del índice de posición de los elementos versus el rango se verá como puntos en línea recta (correlación de 1.0 entre la posición y el rango).

Puede calcular una correlación en estos datos. Para un orden inverso obtendrá -1 y así sucesivamente.

Ha habido excelentes respuestas, y me gustaría agregar un aspecto matemático para completar:

• Puede medir qué tan ordenada está una lista midiendo cuánto está correlacionada con una lista ordenada. Para hacer eso, puede usar la correlación de rango (la más conocida es Spearman ), que es exactamente la misma que la correlación habitual, pero usa el rango de elementos en una lista en lugar de los valores analógicos de sus elementos.

• Existen muchas extensiones, como un coeficiente de correlación (+1 para la clasificación exacta, -1 para la inversión exacta)

• Esto le permite tener propiedades estadísticas para esta medida, como el teorema del límite central permutacional, que le permite conocer la distribución de esta medida para listas aleatorias.

Además del recuento de inversión, para las listas numéricas, la distancia cuadrática media desde el estado ordenado es 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

No estoy seguro del "mejor" método, pero uno simple sería comparar cada elemento con el siguiente, incrementando un contador si element2> element 1 (o lo que quiera probar) y luego dividir por el número total de elementos Debería darte un porcentaje.

Contaría las comparaciones y las dividiría entre el número total de comparaciones. Aquí hay un ejemplo simple de Python .

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result

¿Qué tal algo como esto?

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()

Si toma su lista, calcule los rangos de los valores en esa lista y llame a la lista de rangos Yy otra lista, Xque contiene los enteros de 1a length(Y), puede obtener exactamente la medida de ordenación que está buscando calculando el coeficiente de correlación , r, entre las dos listas.

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}} 

Para una lista completamente ordenada r = 1.0, para una lista ordenada inversamente r=-1.0, y rvaría entre estos límites para distintos grados de ordenación.

Un posible problema con este enfoque, dependiendo de la aplicación, es que calcular el rango de cada elemento de la lista es equivalente a ordenarlo, por lo que es una operación O (n log n).