Cómo medir la "ordenación"

34

Me pregunto si hay una forma estándar de medir la "clasificación" de una matriz. ¿Se consideraría una matriz que tiene el número medio de posibles inversiones máximamente sin clasificar? Con eso quiero decir que está básicamente lo más lejos posible de ser ordenado o revertido.

Robert S. Barnes
fuente

Respuestas:

31

No, depende de su aplicación. Las medidas de clasificación a menudo se refieren como medidas de desorden , que son funciones desde hasta , donde es la colección de todas las secuencias finitas de enteros distintos no negativos. La encuesta realizada por Estivill-Castro y Wood [1] enumera y analiza 11 diferentes medidas de trastorno en el contexto de algoritmos de clasificación adaptativa.N<NRN<N

El número de inversiones puede funcionar para algunos casos, pero a veces es insuficiente. Un ejemplo dado en [1] es la secuencia

n/2+1,n/2+2,,n,1,,n/2

que tiene un número cuadrático de inversiones, pero solo consta de dos carreras ascendentes. Está casi ordenado, pero esto no es capturado por las inversiones.


[1] Estivill-Castro, Vladmir y Derick Wood. "Una encuesta de algoritmos de clasificación adaptativa". Encuestas de computación ACM (CSUR) 24.4 (1992): 441-476.

Juho
fuente
2
El contexto está tratando de entender por qué el ordenamiento rápido funciona relativamente mal en permutaciones aleatorias de n elementos donde el número de inversiones está cerca de la mediana.
Robert S. Barnes
1
Gran ejemplo, esa es exactamente la información que estaba buscando.
Robert S. Barnes
1
Estivill-Castro y la madera es la referencia para este seguro.
Pedro Dusso
10

Mannila [1] axiomatiza la preselección (con un enfoque en algoritmos basados ​​en comparación) de la siguiente manera (parafraseando).

Deje un conjunto totalmente ordenado. Entonces, un mapeo de (las secuencias de elementos distintos de ) a los naturales es una medida de preselección si cumple las siguientes condiciones.ΣmΣΣ

  1. Si está ordenado, entonces .XΣm(X)=0

  2. Si con , y para todo , entonces .X,YΣX=x1xnY=y1ynxi<xiyi<yji,j[1..n]m(X)=m(Y)

  3. Si es una subsecuencia de , entonces .XYΣm(X)m(Y)

  4. Si para todo y para algunos , entonces .xi<yji[1..|X|]j[1..|Y|]X,YΣm(XY)m(X)+m(Y)

  5. m(aX)|X|+m(X) para toda y .XΣaEX

Ejemplos de tales medidas son las

  • número de inversiones,
  • número de permutas,
  • el número de elementos que no son máximos de izquierda a derecha, y
  • la longitud de una subsecuencia creciente más larga (restada de la longitud de entrada).

Tenga en cuenta que se han definido distribuciones aleatorias que utilizan estas medidas, es decir, que hacen que las secuencias que están más / menos ordenadas sean más o menos probables. Estas se llaman distribuciones similares a Ewens [2, cap. 4-5; 3, ejemplo 12; 4], cuyo caso especial es la denominada distribución de Mallows . Los pesos son paramétricos en una constante y cumplenθ>0

Pr(X)=θm(X)YΣΣ|X|θm(Y) .

Observe cómo define la distribución uniforme (para todos los ).mθ=1m

Dado que es posible muestrear permutaciones con estas medidas de manera eficiente, este cuerpo de trabajo puede ser útil en la práctica cuando se comparan los algoritmos de clasificación.


  1. Medidas de preselección y algoritmos de clasificación óptimos por H. Mannila (1985)
  2. Estructuras combinatorias logarítmicas: un enfoque probabilístico de R. Arratia, AD Barbour y S. Tavaré (2003)
  3. Al agregar una lista de números (y otros procesos determinantes dependientes de uno) por A. Borodin, P. Diaconis y J. Fulman (2010)
  4. Distribuciones tipo Ewens y Análisis de Algoritmos por N. Auger et al. (2016)
Rafael
fuente
3

Tengo mi propia definición de "clasificación" de una secuencia.

Dada cualquier secuencia [a, b, c, ...] la comparamos con la secuencia ordenada que contiene los mismos elementos, contamos el número de coincidencias y la dividimos por el número de elementos en la secuencia.

Por ejemplo, dada la secuencia [5,1,2,3,4], procedemos de la siguiente manera:

1) ordenar la secuencia: [1,2,3,4,5]

2) compare la secuencia ordenada con la original moviéndola una posición a la vez y contando el número máximo de coincidencias:

        [5,1,2,3,4]
[1,2,3,4,5]                            one match

        [5,1,2,3,4]
  [1,2,3,4,5]                          no matches

        [5,1,2,3,4]
    [1,2,3,4,5]                        no matches

        [5,1,2,3,4]
      [1,2,3,4,5]                      no matches

        [5,1,2,3,4]
        [1,2,3,4,5]                    no matches

        [5,1,2,3,4]
          [1,2,3,4,5]                  4 matches

        [5,1,2,3,4]
            [1,2,3,4,5]                no matches

                ...

         [5,1,2,3,4]
                 [1,2,3,4,5]            no matches

3) El número máximo de coincidencias es 4, podemos calcular la "clasificación" como 4/5 = 0.8.

La ordenación de una secuencia ordenada sería 1, y la ordenación de una secuencia con elementos colocados en orden inverso sería 1 / n.

La idea detrás de esta definición es estimar la cantidad mínima de trabajo que tendríamos que hacer para convertir cualquier secuencia en la secuencia ordenada. En el ejemplo anterior, necesitamos mover solo un elemento, el 5 (hay muchas formas, pero mover el 5 es el más eficiente). Cuando los elementos se colocarían en orden inverso, tendríamos que mover 4 elementos. Y cuando se ordenó la secuencia, no se necesita trabajo.

Espero que mi definición tenga sentido.

Andrushenko Alexander
fuente
Buena idea. Una definición similar es Exc, la tercera definición de trastorno en el artículo mencionado en la respuesta de Juho . Exc es el número de operaciones requeridas para reorganizar una secuencia en orden ordenado.
Apass.Jack
Bueno, puede ser, acabo de aplicar mi comprensión de la entropía y el desorden a la secuencia de elementos :-)
Andrushenko Alexander
-2

Si necesita algo rápido y sucio (los signos de suma me asustan), escribí una función de desorden súper fácil en C ++ para una clase llamada Array que genera matrices int llenas de números generados aleatoriamente:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

La función simplemente compara el valor de cada elemento con el índice del elemento + 1, de modo que una matriz en orden inverso tiene un valor de desorden de 1, y una matriz ordenada tiene un valor de desorden de 0. No es sofisticado, pero funciona.

Miguel

Michael Sneberger
fuente
Este no es un sitio de programación. Habría sido suficiente definir la noción de desorden y mencionar que se puede calcular en tiempo lineal.
Yuval Filmus