Opération sur des tableaux
Bonjour,
J'essaie de trouver un algo qui permet de faire une opération sur un tableau d'entiers A de taille N.
Les éléments du tableau sont tous différents et compris entre [0 ; N[
L'opération en question est de faire en sorte que A[i] = A[A[i]] avec une complexité en espace de O(1).
Exemple
Entrée : A = 3 2 0 1
Sortie : A = 1 0 3 2
J'ai commencé à faire ceci qui fonctionne sur l'exemple ci-dessus :
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
// Déclarations de variables
int i, val_courant, val_depart;
// Initialisation
i=0;
val_depart = A[i]; // On stocke le 1er élément du tableau dans une variable val_depart
// pour éviter décraser lors de la permutation.
val_courant = A[i]; // Servira de prochain indice
// Tant quon est pas revenu au point de départ on permute
while(val_courant != 0){
A[i] = A[val_courant];
i = val_courant;
val_courant = A[i];
}
// On est arrivé au point de départ, on introduit le 1er élément à la bonne place
A[i] = val_depart; |
Seulement ça ne fonctionne pas sur un tableau quelconque par exemple :
4 0 5 1 3 2 qui donne 3 4 2 0 1 5
Mon programme donne : 3 4 5 0 1 2
Je ne parviens pas à trouver une solution plus générale.
Je fais donc appel à vous pour me permettre d'avoir une idée de départ vers une solution.
Merci d'avance.