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]

Uso de a lo sumo O (1) espacio adicional?

Answer 1

Sí. Partiendo de la posición más a la izquierda, ponemos el elemento que hay en su correcta Posición i mediante el canje con la (otra) elemento fuera de lugar en esa posición i. Aquí es donde necesitamos la O (1) espacio adicional. Mantenemos intercambio de pares de elementos alrededor hasta que el elemento en esta posición es correcta. Sólo entonces se procede a la siguiente posición y hacemos lo mismo.

Ejemplo:

[5 3 2 1 0 4] estado inicial

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

[0 3 2 1 4 5] intercambiados (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] intercambiados (3,1), ahora 1 y 3 son tanto 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:

Debido a 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 por completo.

Answer 2

La solución de Zach es muy bueno.

Sin embargo, me preguntaba por qué no hay ninguna necesidad de clasificar. Si usted tiene la permutación de los índices, utilice los valores como un puntero a la matriz de edad.

Esto puede eliminar la necesidad de ordenar la matriz en el primer lugar. Esto no es una solución que se puede utilizar en todos los casos, pero no tendrán ningún problema 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 a través de los valores en a usted puede hacer algo como (pseudo-código):

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

Si desea colocar a través de los valores en el nuevo orden, hacer:

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

Como se mencionó anteriormente, este soluion puede ser suficiente en muchos casos, pero no pueden, en algunos otros casos. Para otros casos, puede utilizar la solución por Zach.But para los casos en que se puede utilizar esta solución, es mejor porque se necesita no hay que separar en absoluto.