Permutation d'un vecteur

Question

Supposons 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:

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

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

Answer 1

Oui. En partant de la position la plus à gauche, nous avons placé l'élément dans sa position correcte en l'échangeant avec l'élément (autre) mal placé à cette position i. C'est là que nous avons besoin de l'espace supplémentaire O (1). Nous continuons d'échanger des paires d'éléments jusqu'à ce que l'élément dans cette position soit correct. C'est seulement alors que nous passons à la position suivante et faisons 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 la figure 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 ] permuté (3,1), maintenant 1 et 3 sont dans les bonnes positions, passons à la position suivante

[0 1 2 3 4 5] tous les éléments sont dans les bonnes positions, fin.

Remarque:

Depuis 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 au total.

Answer 2

La solution de Zach est très bonne. Pourtant, je me demandais pourquoi il est nécessaire de trier. Si vous avez la permutation des indices, utilisez les valeurs comme un pointeur vers l'ancien tableau.

Cela peut éliminer le besoin de trier le tableau en premier lieu. Ce n'est pas une solution qui peut être utilisée dans tous les cas, mais cela fonctionnera 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 à travers les valeurs un, vous pouvez faire quelque chose comme (pseudo-code):

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

Si vous voulez boucle à travers les valeurs dans le nouvel ordre, faire:

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

Comme mentionné oreille En outre, cette soluion peut suffire dans de nombreux cas, mais peut ne pas l'être dans d'autres cas. Pour les autres cas, vous pouvez utiliser la solution de Zach.Mais pour les cas où cette solution peut être utilisée, c'est mieux car aucun tri n'est nécessaire du tout.