permutación de un vector

Question

Supongamos que tengo un vector:

0 1 2 3 4 5 
[45,89,22,31,23,76] 

Y una permutación de sus índices:

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

¿Hay una manera eficiente de recurrir de acuerdo a la permutación obteniendo así:

[76,31,22,89,45,23] 

Usar como máximo O (1) espacio adicional?

Answer 1

Sí. Comenzando desde la posición más a la izquierda, colocamos el elemento allí en su posición correcta i intercambiándolo con el (otro) elemento extraviado en esa posición i. Aquí es donde necesitamos el O (1) espacio adicional. Continuamos intercambiando pares de elementos hasta que el elemento en esta posición es correcto. Solo entonces pasamos a la siguiente posición y hacemos lo mismo.

Ejemplo:

[5 3 2 1 0 4] estado inicial

[4 3 2 1 0 5] intercambiados (5,4), 5 se encuentra ahora en la posición correcta, pero 4 es todavía mal

[0 3 2 1 4 5] intercambiado (4,0), ahora ambos 4 y 0 están en las posiciones correctas, pasar a la siguiente posición

[0 1 2 3 4 5 ] intercambiaron (3,1), ahora 1 y 3 están en las posiciones correctas, pasar a la siguiente posición

[0 1 2 3 4 5] todos los elementos están en las posiciones correctas, final.

Nota:

Puesto que cada operación de intercambio pone al menos uno (de los dos) elementos en la posición correcta, necesitamos no más de N tales permutas en total.

Answer 2

La solución de Zach es muy buena.

Aún así, me preguntaba por qué hay alguna necesidad de ordenar. Si tiene la permutación de los índices, use los valores como un puntero a la matriz anterior.

Esto puede eliminar la necesidad de ordenar la matriz en primer lugar. Esta no es una solución que se pueda usar en todos los casos, pero funcionará bien en la mayoría de los casos.

Por ejemplo:

a = [45,89,22,31,23,76]; 
b = [5,3,2,1,0,4] 

Ahora si quieres lop través de los valores en un, se puede hacer algo como (pseudo-código):

for i=0 to 4 
{ 
    process(a[i]); 
} 

Si desea recorrer los valores en el orden nuevo, hacer:

for i=0 to 4 
{ 
    process(a[b[i]]); 
} 

Como se mencionó Por lo tanto, esta solución puede ser suficiente en muchos casos, pero puede no serlo en algunos otros casos. Para otros casos, puede usar la solución de Zach.Pero para los casos en los que se puede usar esta solución, es mejor porque no se necesita ninguna clasificación.