Reordenamiento de matriz en el lugar?

Digamos que tengo una matriz de longitud n y una segunda indices matriz, también de longitud n . indices contiene alguna permutación arbitraria de la secuencia [0, n) . Quiero reorganizar a tal que esté en el orden especificado por los indices . Por ejemplo, usando la syntax D:

 auto a = [8, 6, 7, 5, 3, 0, 9]; auto indices = [3, 6, 2, 4, 0, 1, 5]; reindexInPlace(a, indices); assert(a == [5, 9, 7, 3, 8, 6, 0]); 

¿Se puede hacer esto en el espacio O (1) y en el tiempo O (n), preferiblemente sin indices mutación?

Con indices mutación :(. Sin apariencia dura (ver mergesort in situ estable).

 a = [8, 6, 7, 5, 3, 0, 9] indices = [3, 6, 2, 4, 0, 1, 5] for i in xrange(len(a)): x = a[i] j = i while True: k = indices[j] indices[j] = j if k == i: break a[j] = a[k] j = k a[j] = x print a 

Esto es lo que llamo un algoritmo “permutar desde”. En lenguaje similar a C, se vería de la siguiente manera

  for (i_dst_first = 0; i_dst_first < n; ++i_dst_first) { /* Check if this element needs to be permuted */ i_src = indices[i_dst_first]; assert(i_src < n); if (i_src == i_dst_first) /* This element is already in place */ continue; i_dst = i_dst_first; pending = a[i_dst]; /* Follow the permutation cycle */ do { a[i_dst] = a[i_src]; indices[i_dst] = i_dst; i_dst = i_src; i_src = indices[i_src]; assert(i_src != i_dst); } while (i_src != i_dst_first); a[i_dst] = pending; indices[i_dst] = i_dst; } 

Sin embargo, tenga en cuenta que este algoritmo destruye la matriz de index . Lo llamo "permutar desde" ya que el valor del index[i] especifica desde dónde tomar el elemento i-ésimo de la secuencia resultante.

Obsérvese también que el número de operaciones de "movimiento de elementos" requeridas para la permutación in situ de una secuencia es igual al number of misplaced elements + number of cycles in the permutation . Este algoritmo logra este límite, por lo tanto, en términos del número de movimientos, no es posible un algoritmo mejor.

El posible problema con este algoritmo es que se basa en el enfoque de "malabares", lo que hace que su comportamiento de caché no sea óptimo. Entonces, aunque este algoritmo es el mejor en teoría, podría perderse con algunos algoritmos más "prácticos" en la vida real.

También se puede implementar un algoritmo de "permutar a", donde el valor del index[i] especifica dónde reubicar el elemento i-ésimo original.

Si a es una matriz de enteros, entonces es posible un algoritmo O (n) -time, O (1) -space que mantiene el orden de los indices de permutación. En este caso, podemos permutar a en indexes y usar a como almacenamiento temporal de la permutación inversa. Después de realizar la permutación, las matrices a y los indices se intercambian, y los indices se invierten in situ usando, por ejemplo, el algoritmo J de TAoCP . El siguiente es un progtwig de Java que funciona:

 int [] a = {8, 6, 7, 5, 3, 0, 9}; int [] indices = {3, 6, 2, 4, 0, 1, 5}; int n = indices.length; int i, j, m; // permute a and store in indices // store inverse permutation in a for (j = 0; j < n; ++j) { i = indices[j]; indices[j] = a[i]; a[i] = j; } // swap a and indices for (j = 0; j < n; ++j) { i = indices[j]; indices[j] = a[j]; a[j] = i; } // inverse indices permutation to get the original for (i = 0; i < n; ++i) {indices[i] = -indices[i] - 1;} for (m = n - 1; m >= 0; --m) { // for (i = m, j = indices[m]; j >= 0; i = j, j = indices[j]) ; i = m; j = indices[m]; while (j >= 0) {i = j; j = indices[j];} indices[i] = indices[-j - 1]; indices[-j - 1] = m; } 

Esto responde a la pregunta cuando la matriz de indices es mutable.

Aquí hay una solución cuando no es mutable.

 void mutate(int[] input, int[] indices) { int srcInd; for (int tarInd = 0; tarInd < input.length; tarInd++) { srcInd = indices[tarInd]; while(srcInd < tarInd) { // when src is behind, it will have it's final value already and the original // value would have been swapped with src's src pos. Keep searching for the // original value until it is somewhere ahead of tarInd. srcInd = indices[srcInd]; } swap(input, srcInd, tarInd); } } 

Creo que la forma clásica de lidiar con este problema es trabajar en torno a los ciclos, y para ello se necesita un bit marcador por cada elemento de datos de algún lugar. Aquí pellizqué el bit superior de la matriz de índices, que puede restaurar, por supuesto, esto supone que no tiene índices de matriz o está utilizando todos los bits de un número sin firmar como índice. Una referencia para esto es Knuth Volumen 1, sección 1.3.3, respuesta a la pregunta 12, que trata del caso especial de transposición de una matriz. Knuth da referencias a métodos más lentos en el lugar. El documento “Permutando en el lugar” de Fich, Munro y Poblete afirma nlogn time y O (1) espacio en el peor de los casos.

 import java.util.Arrays; public class ApplyPerm { public static void reindexInPlace(int[] rearrangeThis, int[] indices) { final int TOP_BIT = 0x80000000; for (int pos = 0; pos < rearrangeThis.length; pos++) { if ((indices[pos] & TOP_BIT) != 0) { // already dealt with this continue; } if (indices[pos] == pos) { // already in place continue; } // Now shift an entire cycle along int firstValue = rearrangeThis[pos]; int currentLocation = pos; for (;;) { // pick up untouched value from here int replaceBy = indices[currentLocation]; // mark as dealt with for the next time we see it indices[currentLocation] |= TOP_BIT; if (replaceBy == pos) { // have worked our way round rearrangeThis[currentLocation] = firstValue; break; } if ((replaceBy & TOP_BIT) != 0) { throw new IllegalArgumentException("Duff permutation"); } // Move value up rearrangeThis[currentLocation] = rearrangeThis[replaceBy]; // and fill in source of value you have just moved over currentLocation = replaceBy; } } } public static void main(String[] s) { int[] a = new int[] {8, 6, 7, 5, 3, 0, 9}; int[] indices = new int[] {3, 6, 2, 4, 0, 1, 5}; reindexInPlace(a, indices); System.out.println("Result is " + Arrays.toString(a)); } } 

Puedes hacer esto ocultando los valores en la matriz real. De esta manera puede hacer esto en el espacio O (1) y en el tiempo O (n).

Básicamente, primero recorre su matriz de índices, almacena el valor de la matriz de índices en la posición correcta. Ahora esto se puede hacer en el algoritmo de su elección. Para mí, simplemente almacenaría los bits finales del número desde la posición de bit más significativa. Haz esto en un cruce. Ahora la matriz base estaría en mal estado.

Durante la segunda tienda transversal, todas las partes de la mitad superior a la mitad inferior.

La desventaja obvia de esta técnica es que el valor entero almacenado puede contener hasta la mitad de los bits. Es decir, si se trata de un entero de 4 bytes, los valores solo pueden ser de 2 bytes. Sin embargo, en lugar de utilizar hasta la mitad de la matriz como se muestra en el siguiente código, puede mejorarse mediante el uso de un mejor algoritmo donde se oculta el valor en la matriz de índice. Aquí requerirá que los bits máximos reservados en el peor de los casos sean la longitud de la matriz en lugar de la constante 16 en el caso anterior. Funcionará peor que el anterior cuando la longitud excede 2 de potencia 16.

 import java.util.Arrays; class MyClass { public static void main(String[] args) { MyClass myClass = new MyClass(); int[] orig_array = {8, 6, 7, 5, 3, 0, 9}; int[] indices = {3, 6, 2, 4, 0, 1, 5}; myClass.meth(orig_array, indices); } public void meth(int[] orig_array, int[] indices){ for(int i=0;i> 16; System.out.print(Arrays.toString(orig_array)); } } 

Aquí hay una versión de C ++ (modifica los índices):

 #include  #include  template void permutate_from( It const begin, typename std::iterator_traits::difference_type n, ItIndices indices) { using std::swap; using std::iter_swap; for (typename std::iterator_traits::difference_type i = 0; i != n; ++i) { for (typename std::iterator_traits::value_type j = i; ; ) { swap(j, indices[j]); if (j == i) { break; } iter_swap(begin + j, begin + indices[j]); } } } 

Ejemplo:

 int main() { int items[] = { 2, 0, 1, 3 }; int indices[] = { 1, 2, 0, 3 }; permutate_from(items, 4, indices); // Now items[] == { 0, 1, 2, 3 } } 

Versión de JavaScript

 var input = [1,2,3,4,5], specArr = [0,2,1,4,3]; function mutate(input, specArr) { var visited = [0,2] for(var i=0; i