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

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

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.

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.

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

Bonjour picodev,

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

Pour cet algorithme :

Citation:

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

Citation:

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.

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

Citation:

Envoyé par 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[

Citation:

Envoyé par Revaroa

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] ?

Citation:

Envoyé par Revaroa

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 ?

Citation:

Envoyé par Revaroa

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

Citation:

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.

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.

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 )

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

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 ?

Très bonne idée !

Salut,

Je vous remercie pour toutes vos idées.

Citation:

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?

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

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?

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:

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

Citation:

Envoyé par anapurna

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

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:

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:

1 2 3 imax = Max(A[]); ival := (Position*imax)+(A[Position]*imax)+A[[Position]]
Pour retrouver la valeur initiale position

Code:

IvalIni = Divise(ival,imax)-Position

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

Code:

INewVa = Quotient(ival,imax)

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

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.

salut

comment fait tu pour trouver la valeur original avec l'opposé ?
avec la méthode que je décrit on sais que si A[i] > Imax c'est forcement une valeur modifier
et que si l'on a besoin d'une des deux valeur cela est tout a fait réalisable sans grosse difficulté

Effectivement, prendre simplement l'opposé fait de 0 un cas très particulier (si A[0]=0 et si A[0]≠0, le traiter en premier, …
Donc l'idée pour simplifier est d'utiliser l'opposé moins un.

Une implémentation du truc en C pourrait donner :

Bon le code est quick and dirty … pour donner l'idée.

salut

je ne suis pas certain que cela fonctionne tu modifie la valeur du tableau sans possibilité de retrouvé l'ancienne valeur
celle-ci étant perdu impossible a restitué
j'y avais pensé ... mais le fait de positionné le départ et l'arrivé n'est pas bon car la valeur de l'arrivé n'as pas encore servi et de se fait doit être réversible afin de pouvoir utiliser la valeur initial

Il y a forcément au moins un cycle. L'idée est de se souvenir du départ du cycle puis de cycler. Au lieu d'insérer la valeur «finale» on y insère l'opposé de valeur finale moins 1 ce qui permet de ne plus traiter 0 comme un cas particulier car il est envoyé sur -1. Une fois le cycle tourné il faut vérifier qu'il n'y a plus d'autres cycles, i.e. qu'il reste des nombres positifs au quel cas on recommence.
Une fois tous les cycles transformés le tableau ne contient plus que des valeur négatives, - «valeur finale»-1, pour retrouver la vraie valeur finale l'opération est triviale … -( -«valeur finale» - 1 ) - 1 = «valeur finale» +1 -1 = «valeur finale».

Je ne vois pas trop où ce n'est pas correct.

salut

je comprend bien le fait de les mettre en negatif pour ne pas retraiter les valeur deja effectué sauf que
cela revient a faire

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   POUR I DE 0 A HIGH(A[]) FAIRE
     SI A[I] >= 0 ALORS
       j = A[I]
       last  =i;
       REPETER
         tmp = A[j];    // tmp     = A[A[I]] 
         A[j] =-last-1; // A[A[I]] = I   <--- ici c'est pas bon a la deuxième boucle la valeur n'est plus correcte  
         last = j;
        j = tmp;
     JUSQUA  (i = J)
     A[j] = -last-1; // A[A[I]] = I
    FINSI
  FIN FAIRE

Salut,

Citation:

Envoyé par anapurna

avec la méthode que je décrit on sais que si A[i] > Imax c'est forcement une valeur modifier

Donc si A[i] > Imax c'est forcement une valeur modifier cela veut dire qu'on ajoute à tous les éléments du tableau un nombre quelconque ?

Citation:

Envoyé par anapurna

et que si l'on a besoin d'une des deux valeur cela est tout a fait réalisable sans grosse difficulté

Une fois modifier comment faire l'opération A[i] = A[A[i]] ?
Je n'ai pas vraiment compris ta méthode.
Peux-tu me le réexpliquer sur un exemple ou deux s'il te plaît?

Merci.

salut

ma méthode est simple la valeur que j'ecrit n'est pas la valeur voulu mais une formule me permettant de retrouver l'ancienne valeur et la nouvelle
il faut pour cela connaitre la valeur maximal du tableau
une fois cette valeur obtenu il suffit d'utiliser la formule suivante
on ce sert des spécificité de la multiplication et division d'entier

Pour chaque elements du tableau la valeur devrais être de cette ordre
Code:

1 2 3 4 5 6 7 OldValeur = A[Position] ... NewValeur = A[OldValeur] ... Values = (Position+NewValeur)*(imax+1)+OldValeur A[Position] = Values
de cette façon pour retrouver l'ancienne valeur in te suffit de faire

Code:

Oldvaleur = Quotient(values, (imax+1))

et pour retrouver la nouvelle valeur il suffit de faire

Code:

NewValeur = (Values Div (IMax+1)) - Position

Salut,

Citation:

Envoyé par anapurna

NewValeur = (Values Div (IMax+1)) - Position

(Values Div (IMax+1)) signifie Values diviser par (IMax+1) parce que pour l'exemple qui suit je trouve un nombre décimal (la partie entière étant le bon résultat) ?

Exemple :
A = [4, 0, 5, 1, 3, 2];
Pour Position=0.
Code:

1 2 3 4 5 6 imax = 5; Position = 0; OldValeur = A[0]; // 4 NewValeur = A[4]; // 3 Values = (0+3)*(5+1)+4; // 22 A[0] = 22;
Pour retrouver l'ancienne valeur :

Code:

Oldvaleur = Quotient(22, (5+1)); // 4

Pour retrouver la nouvelle valeur :

Code:

NewValeur = (22 Div (5+1)) - 0 // 3,66...

Citation:

Envoyé par Revaroa

(Values Div (IMax+1)) signifie Values diviser par (IMax+1) parce que pour l'exemple qui suit je trouve un nombre décimal (la partie entière étant le bon résultat) ?

on ne parle ici que des partie entiere
Citation:
Envoyé par Revaroa
Exemple :
A = [4, 0, 5, 1, 3, 2];
Pour Position=0.
Code:

1 2 3 4 5 6 imax = 5; Position = 0; OldValeur = A[0]; // 4 NewValeur = A[4]; // 3 Values = (0+3)*(5+1)+4; // 22 A[0] = 22;
Pour retrouver l'ancienne valeur :

Code:

Oldvaleur = Quotient(22, (5+1)); // 4
la on est d'accord sauf que je me suis planté ^^
en faites s'est le mod(22,(5+1)); //=> 4

Citation:

Envoyé par Revaroa

Pour retrouver la nouvelle valeur :

Code:

NewValeur = (22 Div (5+1)) - 0 // 3,66...

oups ici c'est bien le quotient que l'on veut retrouver ... la partie entiere de la division
Quotient(22, (5+1)); //=> 3

j'avais bien précisé ne se servir que des entier mais j'ai répondu un peu vite ce matin

Citation:

Envoyé par anapurna

j'avais bien précisé ne se servir que des entier

Oui c'est vrai tu l'as dis, désolé.

j'ai corrigé ma réponse

j'ai répondu de travers ce matin

on fait un modulo pour trouver le reste de la division
et le quotient pour trouver la parti entière de la division

j'avais pas les neurones bien en place désolé

resalut

voila ce que cela donnerais en pascal

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 
Procedure perm(var arr : array of integer);
var
  i,OldVal,NewVal : integer;
  Imax : Integer;
begin
  Imax := GetMaxValue(arr) +1;
  for i:= low(arr) to High(arr)  do
  begin
    OldVal := arr[i];
    if OldVal >= Imax Then
      OldVal := (OldVal Div Imax)-i;
    NewVal := arr[OldVal];
    if NewVal >= Imax Then
      NewVal := (arr[OldVal] Div Imax)-OldVal;
    arr[i] := (OldVal+i)*Imax + NewVal;
  end;
  // display(arr); uniquement pour le debug 
  for i:= low(arr) to High(arr)  do
    arr[i] :=  arr[i] Mod Imax;
end;

Salut,

Citation:

Envoyé par anapurna

on fait un modulo pour trouver le reste de la division
et le quotient pour trouver la parti entière de la division

Je l'avait deviné :D

Je te remercie beaucoup.

Salut

attention avec cette méthode tu as une limitation de tes indices
correspondant a la racine_carre(de l’étendu de la valeur)
par exemple si tu as un tableau de word (65535) ta valeur maxi ne peut pas dépasser 254 sinon tu risque un débordement (out of range)
pour un entier 2147483647 cela nous donne 46339 ce qui en fait déjà pas mal ;)
et pour un Int64 9223372036854770000 => 3037000499

voila je pense que l'on as fait le tour de la question

On a quand même un peu triché. On s'interdit de créer un 2ème tableau d'entier, mais on s'autorise à utiliser un tableau d'entiers longs 2 fois plus longs que le strict nécessaire.
Si pour une raison ou une autre, les données qu'on reçoit sont stokées sur 1 octet, et que notre tableau fait 100 lignes par exemple, la solution ne marche plus.

Le proposition précédente (remplacer chaque nombre n par -1-n) était aussi un peu malhonnète (besoin de 9 bits là où au départ on avait 8 bits par exemple), mais le débordement est moindre.