Permutation d'un vecteur

Question

suppose que j'ai un vecteur:

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

Et une permutation de ses indices:

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

Y at-il un moyen efficace de recourir en fonction de la permutation obtenant ainsi:

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

En utilisant au plus O (1) espace supplémentaire?

Answer 1

Oui. A partir de la position extrême gauche, nous avons mis l'élément il dans son bon Position i en échangeant avec les (autres) élément déplacé à cette position i. C'est là nous avons besoin de l'O (1) espace supplémentaire. Nous gardons la permutation des paires d'éléments autour jusqu'à ce que l'élément dans cette position est correcte. alors seulement nous procédons à la position suivante et faire la même chose.

Exemple:

[5 3 2 1 0 4] état initial

[4 3 2 1 0 5] échangé (5,4), 5 est maintenant dans la position correcte, mais 4 est encore mal

[0 3 2 1 4 5] échangé (4,0), maintenant les deux 4 et 0 dans les positions correctes, passer à la position suivante

[0 1 2 3 4 5] échangé (3,1), maintenant 1 et 3 sont tous deux en position correcte, de passer à la position suivante

[0 1 2 3 4 5] tous les éléments sont dans la bonne position, à la fin.

Remarque :

Étant donné que chaque opération de swap met au moins un (des deux) éléments dans la bonne position, nous avons besoin de plus de N ces swaps tout à fait.

Answer 2

La solution de Zach est très bonne.

Pourtant, je me demandais pourquoi il y a besoin de trier. Si vous avez la permutation des indices, utiliser les valeurs comme un pointeur vers l'ancien tableau.

Cela peut éliminer la nécessité de trier le tableau en premier lieu. Ce n'est pas une solution qui peut être utilisé dans tous les cas, mais cela fonctionnera très bien dans la plupart des cas.

Par exemple:

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

Maintenant, si vous voulez élaguer par les valeurs , vous pouvez faire quelque chose comme (pseudo-code):

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

Si vous voulez faire une boucle à travers les valeurs du nouvel ordre, faire:

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

Comme mentionné précédemment, ce soluion peut être suffisant dans de nombreux cas, mais ne peut, dans certains autres cas. Pour les autres cas, vous pouvez utiliser la solution par Zach.But pour les cas où cette solution peut être utilisée, il est préférable, car aucun tri est nécessaire à tous.