Discussion :

[souviron34]

Bonjour à tous

J'ai un petit souci d'algorithmie...

Je pose le problème :

• soit un ensemble de points P (N)
  
• soit un ensemble (parcours tronqué) C (M) dans cet ensemble de points (indices dans P)

Je cherche un algo pour stocker dans P(N) au début ET dans le même ordre que spécifié par C(M) ... au vol..


Exemple :

P : 0 2 4 6 8 10 12 14 16 18 20 22 (N=12)

C : 7 2 3 1 5 4 (M=6)

Je cherche à avoir un algo pour obtenir :

P : 12 2 4 0 8 6 ...

(P(7), P(2), P(3), P(1), P(5), P(4))


Je peux passer par une variable intermédiaire, mais j'amerais ne pas passer par un tableau intermédiaire..

Si vous avez des idées, je les accepte avec plaisir

Parce que je sèche un peu là...


Si les indices étaent croissants, ce serait facile..

Mais non seulement ils ne sont pas croissants, mais ils peuvent être < M ... et même à eux-même : indice(4) = 1

[nsanabi]

je ne pense as que cela soit possible sans passer par un autre tableau,
au cour d'un traitement normal de remplacement, il y'aura beaucoup de cases à stocker en attendant une possible réutilisation

[Nemerle]

Un truc débile: pour chaque i de 1 à M tu échanges P(i) avec P(C(i)), et tu remplaces éventuellement i par C(i) dans la liste des C(j) avec j>i.

Ca répond à ton problème?

[pseudocode]

Je plussoie la proposition de Nemerle

Tu peux meme renuméroter ton tableau de swap (C[]) avant de faire les permutation de ton tableau de départ.

Code java :

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

1
2
3
4
5
6
7
8
9
10
 
// swap table renumbering
for(int i=0;i<M;i++)
	for(int j=i+1;j<M;j++)
		if (C[j]==i) C[j]=C[i];
 
// swapping elements
for(int i=0;i<M;i++) {
	int swap=P[i]; P[i]=P[C[i]]; P[C[i]]=swap;
}

[souviron34]

merci

je vais essayer ça ..

J'avais réussi à trouver un algo, sauf quand M = N ..

Je vous reviendrais là-dessus plus tard..

[souviron34]

bon

de retour..

Je n'ai pas réussi à faire marcher cet algo (mais je réessayerais peut-être ce week end).. Mais je crois que ça ne marche pas si il y a une réciprocité :
C(1) = 3
C(3) = 1



Mais j'ai trouvé !!! Après 4 ou 5 jours de réflexions, d'essais, et d'échecs successifs...

On calcule le poiint ayant l'indice minimum

On shifte C jusqu'à ce que ce point soit en 0

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
 
  n3 = NPts ;
  k = -1 ;
  for ( i = 0 ; i < M ; i++ )
    {
       if ( C[i] <= n3 )
         {
	  if ( C[i] < i )
	    {
	        n3 = C[i] ;
	        k = i ;
	    }
         }
    }
 
  if ( k >= 0 )
    {
        for ( i = (M-1) ; i >= k ; i-- )
           {
	      l = C[M-1] ;
 
	      for ( j = (M-2) ; j >= 0 ; j-- )
	           C[j+1] = C[j] ;
 
	      C[0] = l ;
           }
    }

Pour M = N, je n'ai pas le choix que de passer par un tableau intermédiaire..

Merci à tous..