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).

[Revaroa]

On travaille dans [0;N[ ou [1;N] ?

Désolé je me suis trompé, on travaille dans [0;N[

Ok, je vais réfléchir sur tous ce qui a été dit.

Si comme moi vous être en train de déjeuner.
Bon appétit.

Je reviendrai plus tard.
Merci.

[picodev]

Je crois que je viens de comprendre ton problème. On te donne un tableau P de taille N qui est une permutation de [0;N[. À partir de ce tableau tu dois donner un tableau A de taille N qui est aussi une permutation de [0;N[ mais qui en plus a la propriété A[i]=A[A[i]] pour tout i de [0;N[.

Si c'est ça c'est bien plus simple.

[Revaroa]

Oui c'est à peu près ça.
On me donne un tableau A de N éléments tels que les éléments x tous différents soient dans l'intervalle 0 ≤ x < N (autrement dit x ∈ [0;N[ )
Je dois réorganiser le tableau de telle sorte que A[i] devienne A[A[i]].
Cette réorganisation doit se faire avec une complexité en espace de O(1).
Exemple que j'ai donné au début :
Entrée : A = {3; 2; 0; 1}
A[0] = A[3]
A[1] = A[2]
A[2] = A[0]
A[3] = A[1]
Sortie : A = {1; 0; 3; 2}
Mais ce que j'ai fait fonctionne pour cet exemple seulement et j'essaie de trouver une autre solution qui marche pour n'importe quel tableau qui respecte les contraintes cités ci-dessus. (Un tableau de N éléments tels que les éléments x tous différents soient dans l'intervalle 0 ≤ x < N )

[François DORIN]

Bonjour,

Je ne suis pas sur qu'il existe une solution en O(1) en espace.

Une semble qu'une solution existe dès lors que toutes les permutations sont liées, de sortes qu'en "sautant" d'un Ai un AAi on puisse itérer sur tous les éléments du tableau.

Maintenant, prend l'exemple suivant : A=[1, 2, 0, 3, 5, 4]. La solution est [2, 0, 1, 3, 4, 5]. On peut voir ici qu'il y a 2 sous-groupes de permutation :

• Les 3 premières colonnes ne permutent qu'entre elles ;
• Les 3 dernières colonnes ne permutent qu'entre elles également.

C'est à dire que toute solution basé sur la détermination de l'indice suivant à examiner est vouée à l'échec, car la transformation ne sera alors que partielle (si tu détermines l'indice suivant tu vas rester dans le sous-groupe actuellement en cours de traitement).

Pour pouvoir traiter tous les "sous-groupes", il faudrait avoir une mémoire des indices déjà traités par exemple, ce qui exclue un algo en O(1) en espace...

[picodev]

Ou «marquer» les nombres déjà traités en changeant leur signe … ce qui implique de commencer par mettre le 0 `a la bonne place.
Une dernière passe rend tous les nombres positifs pour obtenir le résultat ?

[François DORIN]

Très bonne idée !

[Revaroa]

Salut,

Je vous remercie pour toutes vos idées.

Ou «marquer» les nombres déjà traités en changeant leur signe … ce qui implique de commencer par mettre le 0 `a la bonne place.
Une dernière passe rend tous les nombres positifs pour obtenir le résultat ?

Peux-tu développer sur un exemple s'il te plaît?

[Revaroa]

Si par exemple A = {4;0;5;1;3;2}
Commencer par mettre 0 à la bonne place signifie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Chercher l'élément 0 dans le tableau On trouve 0 à l'indice i = 1;
Chercher la place de 0 dans le tableau 
place = A[A[A[i]]];    // A[A[A[1]]] = A[A[0]] = A[4] = 3 
A[place] = A[i];    // A[3] = A[1]
// Jusqu'ici 0 est à la bonne place mais avant de mettre 0 à la bonne place,
// il faut que je stocke la valeur à A[place] pour ne pas l'écraser :
temp = A[place];
A[place] = A[i]; 

Ensuite, j'ai essayé des tas de choses y compris changer le signe des nombres déjà traités mais sans aboutir aux résultats pour n'importe quel tableau en entrée.
J'applique surement pas correctement cette idée de changer de signe?

[anapurna]

salut,

pourquoi se compliquer la vie pour dire si la case est deja marqué ou pas
comme on te la dis le plus simple est de passer par un autre tableau de même dimension et une simple boucle suffira a te donner ton résultat donc ton algo seras bien en O(1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
element = 0 
TANSQUE element < Lonqueur(A) Faire 
  B[element] := A[A[element]]
  element = element+1
FINTANSQUE 
 
RETOURNER B

[François DORIN]

pourquoi se compliquer la vie pour dire si la case est deja marqué ou pas
comme on te la dis le plus simple est de passer par un autre tableau de même dimension et une simple boucle suffira a te donner ton résultat donc ton algo seras bien en O(1)

Peut être parce qu'il a bien précisé algo en O(1) en espace

[anapurna]

salut,

dans ce cas ce n'est pas la bonne méthode pour le réaliser
car on utilise la position de la valeur et la valeur de la position
pour bien faire il faut pouvoir modifier la valeur en A[position] = A[A[position]]
ce qui nous fait perdre l'ordre des éléments et leur valeur associé
si tu n'as pas un "historique" des éléments remplacés je vois pas bien comment tu peut t'en sortir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Reprenons l'exemple  :
4, 0, 5, 1, 3, 2
à la premier boucle tu remplace la valeur 0 par la 4ieme valeur soit 3 
la deuxième boucle on prend la valeur en 0 sauf que celle-ci a changé entre temps elle est passé de 4 a 3

donc tu perd ton "historique"

pour y arriver, je pense qu'il faut utiliser la valeur max de ton indice afin de pouvoir y associer ton nouvelle indice et l'ancien
mais ceci ne pourras ce faire qu'avec au minimum deux boucle
la première recalculant les indices et la seconde pour les enlever
ce qui je pense revient a indicer tes éléments comme suit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
   imax = Max(A[]);
   ival := (Position*imax)+(A[Position]*imax)+A[[Position]]

Pour retrouver la valeur initiale position

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

IvalIni  = Divise(ival,imax)-Position

pour la nouvel position c'est le reste de la division

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 INewVa = Quotient(ival,imax)

a mon avis c'est le seul moyen de pouvoir retrouver tes éléments sans recréer un nouveau tableau

[picodev]

En effet, pour savoir si un élément a ou non été «bougé» il faut modifier sa valeur de telle sorte qu'à la fin on puisse retrouver la valeur originelle.
Ensuite que tu ajoutes une valeur ou que tu prennes l'opposé ça revient au même. L'opposé fonctionne ici car au départ tous les nombres sont positifs.