Discussion :

[Revaroa]

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.

[tbc92]

Tu dis à un moment :'Tant qu'on n'est pas revenue au point de départ on permute,

Ce principe ne me semble pas adapté.

Prend par exemple A = 1 0 2 3
Voire A = 0 2 3 1

[Revaroa]

Bonjour,

Tout d'abord merci de répondre à mon post.
Effectivement, le principe n'est pas du tout adapté.
J'y réfléchis encore.

[picodev]

Bonjour,
si tu désires garder la contrainte d'espace O(1) alors peu importe l'entrée. Tu pars toujours du tableau trié, dans ton cas {0,1,…,n-1} puis tu swappes deux éléments, chaque élément n'étant swappé qu'une seule fois. Donc un algorithme simple consiste par exemple à swapper un élément avec son suivant s'il existe. Tu obtiendras toujours
{1,0,3,2,4} pour un tableau à 5 éléments. Une autre solution consiste à faire un swap «à la palindrome» → {4,3,2,1,0}.
D'uune manière plus générale toute bijection f de [0;N[ dans lui-même telle que f(x)=f(f(x)) et f est en O(1) convient. La seconde idée correspond à f(x)=N-x-1, la première est un peu plus compliquée et dépend de la parité de N.

[tbc92]

Ici, tu cherches à faire la manip sans utiliser une autre variable ou un autre tableau. Ca doit pouvoir se faire, mais c'est galère.

Tu as la solution toute simple (syntaxe à revoir, mais c'est ton job ) :

function autopermute( A )
int t ;
array B ;

t = length(A)
for (i = 0 ; i< t ; i++)
B[i] = A [ A[i] ]
next
return B

[Revaroa]

Bonjour picodev,

Pour commencer merci.
Ensuite, tu me dis si j'ai pas bien compris.

Pour cet algorithme :

Tu pars toujours du tableau trié, dans ton cas {0,1,…,n-1} puis tu swappes deux éléments, chaque élément n'étant swappé qu'une seule fois. Donc un algorithme simple consiste par exemple à swapper un élément avec son suivant s'il existe. Tu obtiendras toujours
{1,0,3,2,4} pour un tableau à 5 éléments.

Pour un tableau trié {1,2,3,4}
Pour f(x) = f(f(x)), si on commence par x=1
f(1) = f(f(1))
or f(1)=1
alors f(1)=f(1)
Même chose pour le reste.
Donc il n'y a pas besoin de swappé.

La seconde idée correspond à f(x)=N-x-1, la première est un peu plus compliquée et dépend de la parité de N.

La première est un peu plus compliquée alors je préfère celle-ci
Mais si je fais un test sur l'exemple posté par tbc92
A = {0,2,3,1} le résultat doit être {0,3,1,2}
Or, Pour f(x)=N-x-1
f(0)=4-0-1 = 3
f(1)=4-1-1 = 2 ...
Ce qui donnerai {3,2,1,0} ≠ {0,3,1,2}

Peut-être j'ai pas compris ce que tu essaie de me dire.

[Revaroa]

tbc92 la fonction autopermute utilise un autre tableau, la contrainte O(1) en espace n'est plus respectée.

[picodev]

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[

Bonjour picodev,

Pour commencer merci.
Ensuite, tu me dis si j'ai pas bien compris.

Pour cet algorithme :


Pour un tableau trié {1,2,3,4}

Ça commence mal si tu ne respecte pas tes propres contraintes
On travaille dans [0;N[ ou [1;N] ?

Pour f(x) = f(f(x)), si on commence par x=1
f(1) = f(f(1))
or f(1)=1
alors f(1)=f(1)
Même chose pour le reste.
Donc il n'y a pas besoin de swappé.

Comme je le disais peu importe le tableau de départ, tu pourrais lui donner n'importe quelles données tu auras toujours le même tableau en sortie. L'ordre du tableau initial n'a aucune importance, d'où l'idée de partir du tableau trié soit toujours {0,1,…,N-1}.

À moins que tu veuilles quelque chose de différent ?

tbc92 la fonction autopermute utilise un autre tableau, la contrainte O(1) en espace n'est plus respectée.

Au cas où … O(1) ne signifie pas «aucune variable», O(1) signifie «autant de variables qu'on veut à partir du moment où leur nombre ne dṕend pas de la taille du tableau». Un algo qui aurait besoin d'un tableau secondaire de 100¹⁰⁰ éléments serait toujours en O(1).