arrays - programacion - ¿Es posible invertir una matriz con espacio extra constante?

matrices en matlab programacion

Question

Digamos que tengo una matriz A con n elementos únicos en el rango [0, n) . En otras palabras, tengo una permutación de los enteros [0, n).

¿Es posible transformar A en B usando O (1) espacio extra (también conocido como AKA en el lugar) de manera que B [A [i]] = i ?

Por ejemplo:

       A                  B
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4]

Answer 1

Invertir una matriz A requiere que encontremos una permutación B que cumpla con el requisito A[B[i]] == i para todo i .

Para construir el inverso en el lugar, tenemos que intercambiar elementos e índices configurando A[A[i]] = i para cada elemento A[i] . Obviamente, si simplemente iteráramos en A y realizáramos el reemplazo mencionado, podríamos anular los próximos elementos en A y nuestro cálculo fallaría.

Por lo tanto, tenemos que intercambiar elementos e índices a lo largo de los ciclos de A siguiendo c = A[c] hasta que alcancemos el índice de inicio de nuestro ciclo c = i .

Cada elemento de A pertenece a uno de esos ciclos. Dado que no tenemos espacio para almacenar si un elemento A[i] ya ha sido procesado y debe omitirse, debemos seguir su ciclo: Si alcanzamos un índice c < i , sabríamos que este elemento es parte de Un ciclo previamente procesado.

Este algoritmo tiene una complejidad en el peor tiempo de ejecución de O (n²) , una complejidad promedio en el tiempo de ejecución de O (n log n) y una complejidad en el mejor caso de ejecución de O (n) .

function invert(array) {
  main:
  for (var i = 0, length = array.length; i < length; ++i) {
    
    // check if this cycle has already been traversed before:
    for (var c = array[i]; c != i; c = array[c]) {
      if (c <= i) continue main;
    }
    
    // Replacing each cycle element with its predecessors index:
    var c_index = i, 
        c = array[i];
    do {
      var tmp = array[c];
      array[c] = c_index; // replace
      c_index = c; // move forward
      c = tmp;
    } while (i != c_index)
      
  }
  return array;
}
  
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]

Ejemplo para A = [1, 2, 3, 0] :

1. El primer elemento 1 en el índice 0 pertenece al ciclo de los elementos 1 - 2 - 3 - 0. Una vez que cambiamos los índices 0, 1, 2 y 3 a lo largo de este ciclo, hemos completado el primer paso.

2. El siguiente elemento 0 en el índice 1 pertenece al mismo ciclo y nuestro control nos lo dice en un solo paso (ya que es un paso hacia atrás).

3. Lo mismo se aplica a los elementos restantes 1 y 2 .

En total, realizamos 4 + 1 + 1 + 1 ''operaciones''. Este es el mejor de los casos.

Answer 2

Sí, es posible, con el algoritmo de tiempo O (n ^ 2):

Tome el elemento en el índice 0, luego escriba 0 en la celda indexada por ese elemento. Luego use solo el elemento sobrescrito para obtener el siguiente índice y escriba el índice anterior allí. Continúe hasta que vuelva al índice 0. Este es el algoritmo de ciclo líder.

Luego haga lo mismo a partir del índice 1, 2, ... Pero antes de realizar cualquier cambio, realice el algoritmo de líder de ciclo sin ninguna modificación a partir de este índice. Si este ciclo contiene algún índice debajo del índice de inicio, simplemente omítalo.

O este algoritmo de tiempo O (n ^ 3):

Tome el elemento en el índice 0, luego escriba 0 en la celda indexada por ese elemento. Luego use solo el elemento sobrescrito para obtener el siguiente índice y escriba el índice anterior allí. Continuar hasta volver al índice 0.

Luego haga lo mismo a partir del índice 1, 2, ... Pero antes de realizar cualquier cambio, realice el algoritmo de líder de ciclo sin ninguna modificación a partir de todos los índices anteriores. Si el índice actual está presente en cualquier ciclo anterior, simplemente omítalo.

He escrito (ligeramente optimizado) la implementation del algoritmo O (n ^ 2) en C ++ 11 para determinar cuántos accesos adicionales se necesitan para cada elemento en promedio si se invierte la permutación aleatoria. Aquí están los resultados:

size accesses
2^10 2.76172
2^12 4.77271
2^14 6.36212
2^16 7.10641
2^18 9.05811
2^20 10.3053
2^22 11.6851
2^24 12.6975
2^26 14.6125
2^28 16.0617

Mientras que el tamaño crece exponencialmente, el número de accesos a elementos crece de forma casi lineal, por lo que la complejidad del tiempo esperado para permutaciones aleatorias es algo como O (n log n).