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 : 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 qu’on 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.