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 :
Seulement ça ne fonctionne pas sur un tableau quelconque par exemple :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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;
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.
Partager