Discussion :

[anapurna]

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é

[picodev]

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 :

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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
 
void perm(size_t size, int array[static size])
{
  for(size_t i=0; i<size; ++i) {
    if (array[i]<0)
      continue;
    size_t j=array[i];
    size_t last=i;
    do {
      int tmp=array[j];
      array[j]=-last-1;
      last=j;
      j=tmp;
    } while (i!=j);
    array[j] = -last-1;
  }
  for(size_t i=0; i<size; ++i)
    array[i]=-array[i]-1;
}
 
void display(size_t size, int array[static size])
{
  putchar('[');
  for(size_t i=0; i<size; ++i)
    printf(" %d", array[i]);
  puts(" ]");
}
 
int main(void)
{
  int disp[]={0,1,2,3,4,5,6};
  int test[]={1,2,6,3,0,5,4};
  size_t size=sizeof test/sizeof *test;
 
  printf("Le nombre : ");
  display(size, disp);
  printf("va en     : ");
  display(size, test);
  printf("résultat  : ");
  perm(size,test);
  display(size, test);
 
  return 0;
}

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

[anapurna]

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

[picodev]

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.

[anapurna]

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 :

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

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

[Revaroa]

Salut,

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 ?

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.

[anapurna]

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 :

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

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 :

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

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

et pour retrouver la nouvelle valeur il suffit de faire

Code :

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

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

[Revaroa]

Salut,

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 :

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

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 :

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

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

Pour retrouver la nouvelle valeur :

Code :

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

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

[anapurna]

(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

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

Code :

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

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 :

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

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

Pour retrouver la nouvelle valeur :

Code :

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

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

[Revaroa]

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

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

[anapurna]

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é

[anapurna]

resalut


voila ce que cela donnerais en pascal

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

[Revaroa]

Salut,

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é

Je te remercie beaucoup.

[anapurna]

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

[tbc92]

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.