Permutação de um vetor

Question

suponho que eu tenho um vetor:

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

E uma permutação de seus índices:

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

Existe uma maneira eficiente de recorrer lo de acordo com a permutação obtendo assim:

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

Usando no máximo O (1) espaço adicional?

Answer 1

Sim. A partir da posição mais à esquerda, colocamos o elemento lá na sua correta posição i, trocando-a com o (outro) elemento perdido nessa posição i. Isto é onde precisamos do O (1) espaço adicional. Nós mantemos a troca de pares de elementos ao redor até que o elemento nesta posição é correta. Só então é que vamos avançar para a próxima posição e fazer a mesma coisa.

Exemplo:

[5 3 2 1 0 4] estado inicial

[4 3 2 1 0 5] trocado (5,4), 5 está agora na posição correcta, mas 4 ainda não está correcto

[0 1 2 3 4 5] trocado (4,0), agora tanto 4 0 e estão nas posições correctas, mover para a próxima posição

[0 1 2 3 4 5] trocado (3,1), agora 1 e 3 estão ambos nas posições correctas, mover para a próxima posição

[0 1 2 3 4 5] todos os elementos estão nas posições correctas, final.

Nota :

Uma vez que cada um de swap coloca operação pelo menos um (dos dois) elementos na posição correta, nós não mais do que N tais swaps ao todo precisa.

Answer 2

A solução de Zach é muito bom.

Ainda assim, eu queria saber porque é que há qualquer necessidade de tipo. Se você tem a permutação dos índices, usar os valores como um ponteiro para a matriz de idade.

Isto pode eliminar a necessidade de classificar a matriz em primeiro lugar. Esta não é uma solução que pode ser usado em todos os casos, mas ele vai funcionar bem na maioria dos casos.

Por exemplo:

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

Agora, se você quiser lop através dos valores em a , você pode fazer algo como (pseudo-código):

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

Se você quiser percorrer os valores na nova ordem, fazer:

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

Como mencionado anteriormente, este soluion pode ser suficiente em muitos casos, mas não pode, em alguns outros casos. Para outros casos, você pode usar a solução por Zach.But para os casos em que esta solução pode ser usado, é melhor porque nenhuma classificação é necessária a todos.