Cómo medir la "ordenación"

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.

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^{<N}$$\mathbb{R}$$N^{<N}$

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

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.

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.$\Sigma$$m$$\Sigma^{\star}$$\Sigma$

1. Si está ordenado, entonces .$X \in \Sigma^{\star}$$m(X) = 0$

2. Si con , y para todo , entonces .$X,Y \in \Sigma^{\star}$$X = x_1 \dots x_n$$Y = y_1 \dots y_n$$x_i < x_i \iff y_i < y_j$$i,j \in [1..n]$$m(X) = m(Y)$

3. Si es una subsecuencia de , entonces .$X$$Y \in \Sigma^{\star}$$m(X) \leq m(Y)$

4. Si para todo y para algunos , entonces .$x_i < y_j$$i \in [1..|X|]$$j \in [1..|Y|]$$X,Y \in \Sigma^{\star}$$m(X \cdot Y) \leq m(X) + m(Y)$

5. $m(a \cdot X) \leq |X| + m(X)$ para toda y .$X \in \Sigma^{\star}$$a \in E \setminus X$

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$\theta > 0$

$\qquad\displaystyle \operatorname{Pr}(X) = \frac{\theta^{\,m(X)}}{\sum_{Y \in \Sigma^{\star} \cap \Sigma^{|X|}} \theta^{\,m(Y)}}$ .

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

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)

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.

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