Discussion :

[Steph82]

Slt,
j'ai un tableau a 2 dimensions. Je dois placer dessus N objets a des endroits differents, sans que d'une part il y est 2 objets sur la même case, et d'autres part je ne peux pas placer les objets sur certaines cases, qui sont inappropriés.

Y'a t-il un algorithme à suivre ? plusieurs ? quelle est la mailleur solution ?

Merci.

[Kangourou]

salut,

je crois que la meilleure solution c'est de choisir tes cases au fur et a mesure, de tester si elles n'ont pas deja ete choisies et si la case et valide, puis de repeter la procedure N fois.

les solutions plus elaborees vont dependre de la disposition et du nombre de cases interdites. Si elles sont regroupees en blocs, tu pourras simplifier les tests.
Si il y a vraiement beaucoup plus de cases interdites que de cases libres, tu peux faire une iteration sur les cases du tableau pour compter le nb M de case libres, et choisir un nombre entre 1 et M qui te donnera la place de la prochaine case a placer. Mais a mon avis la premiere methode reste plus simple.

A+

[Steph82]

je crois que la meilleure solution c'est de choisir tes cases au fur et a mesure, de tester si elles n'ont pas deja ete choisies et si la case et valide, puis de repeter la procedure N fois.

Si je fais ca, ca ne sera pas aleatoire car parcourant mon tableau via 2 boucles imbriquées, ca va être quasiment des cases adjacentes.
Le mieux a mon avis c'est de tirer N cases au pif parmi toutes les cases valides. En faite je prends N case valides parmi l'ensemble de toutes mes cases de mon tableau. Mais je ne vois pas trop comment representer cet ensemble.

[grishka]

pour obtenir N indices distinct au hasard, on peut utiliser un algo de ce type (en O(n) ) qui reprend ton idée:

1-récupèrer l'ensemble des indices des emplacements libre du tableau
2-effectuer plusieurs permutations aléatoire sur cet ensemble.
3-récupèrer les N premiers indices

[Kangourou]

en fait, quand je disais de choisir tes cases au fur et a mesure, c'est de choisir x entre 1 et XMAX, de choisir y entre 1 et YMAX, et de faire les tests sur la case de coordonnees (x,y). Dans ce cas c'est du hasard, et meme si tu passes un tirage ca reste aleatoire.

Mais tu peux aussi choisir entre 1 et XMAX*YMAX et calculer x et y en fonction de ce nombre, ca revient au meme.

a+

[Steph82]

En fait j'ai peut etre trouvé la solution:
1) Je tire au hasard N
2) Je crée un tableau dynamique de pointeurs de taille X(X étant le nombre de cases valides)
3) Je parcours tte mes cases et je les pointes ds mon tableau s'il est son valides.
4) Je tire un nombre M au hasard compris entre 0 et N-1
5) Je place mon objet a la case pointé d'indice M
6) Je permute les pointeurs de mon tableau dynamique entre celui d'indice M et l dernier
7) j'ffectue 4) de 0 a N-2
....

Merci pour vos réponses

[sbadecoder]

Moi, j'utiliserai
un tableau avec un record
ex:

Type
T_Case =
Record
Vide : Boolean;
Possible : Boolean;
...
End;


Array[1..100]Of T_case;

Puis tu fais une boucle
repeat until
jusqu'à ce que le nombre tiré au hasard soit ok.

[Steph82]

Ouais mais imagine un tableau 200*200 avc une 3 cases valides. Ca peut tourner un moment avant de trouver la bonne.

[grishka]

Steph82, ton algo est bon à priori et évite la boucle de recherche d'une case valide. Une petite remarque cela dit :

point 7 : tu dois recommencer le tirage sur [0,N-1] (au point 4, le nombre N-1 n'est peut-être pas sorti) mais le point important est de réaliser suffisament de permutations. Je pense que N permutations suffiront.

De plus il faut vérifier que N<=X...

[Steph82]

Oui, je l'ai pas mis ms cela va de soi, sinon bonjour le poiteur qui se barre du tableau, ou qui replace un objet sur une case déjà defini.
C'est clair au pire j'ai N permutation, et de plus j'avance dans mon algo, plus le tablau se rétréci pour le tirage (façon de parler, il ne se rétréci pas en mémoire), dc plus c'est rapide .
Je crois que c'est bon, merci de votre aide.