Algorithme de remplissage correct

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 :D

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

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

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?

Je plussoie la proposition de Nemerle :ccool:

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

Code:

---

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

---

merci :ccool:

je vais essayer ça ..

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

Je vous reviendrais là-dessus plus tard..

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

On calcule le poiint ayant l'indice minimum

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

Code:

---

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

Re-bonjour..

Encore 2 petites questions...

• Tout d'abord, dans un algo tel que celui-ci :
  
  
  Code:

  ---

  1 2	for(int i=0;i<M;i++) for(int j=i+1;j<M;j++)

  ---

  Quelle est la complexité ?
  
  
  
• Comment dénote-t-on la complexité de calcul ("computational complexity") ?
  
  Par exemple si j'ai :
  
  
  Code:

  ---

  1 2 3 4

  for ( i = 0 ; i < N ; i++ )     for ( i = 0 ; i < N ; i++ )

  ---

  En temps c'est bien en O(N), mais en calcul c'est 2*N ..
  
  De même si on a :
  
  
  Code:

  ---

  1 2 3 4

  for ( i = 0 ; i < N ; i++ )     qsort

  ---

  En temps c'est bien O(N log(N)), mais en calcul c'est (N + Nlog(N))
  
  ?
  

Citation:

---

Envoyé par souviron34

[LIST][*]Tout d'abord, dans un algo tel que celui-ci :

Code:

---

1 2	for(int i=0;i<M;i++) for(int j=i+1;j<M;j++)

---

Quelle est la complexité ?

---

compléxité ~= M + (M-1) + (M-2) + ... + 1 = M(M+1)/2 = O(M²)

Citation:

---

[*]Comment dénote-t-on la complexité de calcul ("computational complexity") ?

Par exemple si j'ai :

Code:

---

1 2 3 4

for ( i = 0 ; i < N ; i++ )     for ( i = 0 ; i < N ; i++ )

---

En temps c'est bien en O(N), mais en calcul c'est 2*N ..

---

Oui, il y a 2*N tours de boucle et c'est bien en O(N) (c-a-d dominé par k.N, avec k>0 - en l'occurrence k=2).

Peut-être devrais tu regarder les notations "big Theta" ou "~" qui parlent d'équivalence et pas de domination.

:arrow: http://en.wikipedia.org/wiki/Big_O_n...ndau_notations

Citation:

---

De même si on a :

Code:

---

1 2 3

for ( i = 0 ; i < N ; i++ )   qsort

---

En temps c'est bien O(N log(N)), mais en calcul c'est (N + Nlog(N))

---

Idem. O(N log(N)) = O(N + Nlog(N))

L'un domine l'autre (pour un facteur k et à partir d'un rang N), et réciproquement.