Discussion :

[khayyam90]

bien le bonjour

mon problème est le suivant :
je dois effectuer un traitement sur toutes les cases d'un tableau mais je ne peux pas parcourir mon tableau case après case.

Ma contrainte est que la case sur laquelle je fais le traitement doit être choisie alétoirement. Et je dois traiter toutes les cases.

En gros, actuellement j'ai mon tableau et un tableau miroir contenant des booléens symbolisant si le traitement a déjà été fait ou non sur la case miroir. Et j'ai un compteur de cases déjà traitées.

j'en suis là

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 TANT QUE mon nombre de cases traitées < nb total de cases à traiter
 
choisir une case aléatoire
vérifier que cette case n'a pas déjà été traitée en regardant la case miroir.
SI la case choisie a déjà été traitée, 
    on boucle jusqu'à  ce qu'on en trouve une pas encore traitée
FINSI
 
    je fais mon traitement
    case miroir = oui.
 
nombre_de_cases_traitées++
FIN TANT QUE

mais le gros soucis de cette méthode est que pour les tableaux assez volumineux, il faudra un grand nombre de tours de boucles "dans le vent" pour obtenir les dernières cases qui restent à traiter, il mettra du temps à les trouver ; et bien sûr l'algo prend vite beaucoup de temps.

j'espère m'être fait comprendre.
quelqu'un a-t-il une solution à me proposer ?

[2Eurocents]

Tu peux conserver une liste des indices des valeurs non-traitées, mettons sous forme d'un tableau.
A chaque itération, tu prends un élément au hasard dans cette liste, tu le traites, et tu le supprimes de ta liste des indices des valeurs non-traitées (décalage des valeurs suivantes par dessus)
Attention !!! La suppression diminue le nombre d'éléments de ce tableau, il faut en tenir compte pour le tirage aléatoire suivant ...

Comme ça, tu traite une valeur à chaque tirage ...

[Mac LAK]

Une autre solution peut être un mélange dans le genre "shuffle".

Base de départ : une LUT simple de cardinalité N (N étant le cardinal de ton tableau d'origine), avec LUT(i)=i.

Tu vas mélanger cette LUT en permutant de manière aléatoire ses éléments (par paires), et ceci un nombre suffisant de fois pour approcher un mélange complet aléatoire (2*N permutations devraient suffire, peut-être un peu plus si tu constates trop de séquences continues).

Ensuite, tu n'as qu'à parcourir ta LUT séquentiellement, et traiter dans ton tableau d'origine l'élément LUT(i), ce qui aura pour effet de traiter ton tableau de manière aléatoire sans risquer de retomber sur un élément déjà traité, ni d'avoir "du mal" à trouver une case non-traitée.

[Guigui_]

tu peux aussi te créer un autre tableau (tabparcours) ayant autant de case que ton tableau à traiter (tab)
puis tu le remplis par des nombres de 0 à la longueur de ton tableau

Code :

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

for i=0 to longueur(tabparcours)-1: tabparcours[i]=i

puis tu permutes toutes les cases (la ième avec une choisis aux hasards)

Code :

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

1
2
for i=0 to longueur(tabparcours)-1:
    swap(tabparcours,i,rand(len(tabparcours(i)))

enfin, tu n'as plus qu'à traiter ton tableau (tab) avec le parcours de tabparcours

Code :

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

1
2
for i=0 to len(tabparcours)-1:
     traiter(tab[tabparcours[i]])

Edit: enh fait ce que je propose est la même chose que ce que propose Mac_Lak sauf qu'il n'y a besoin que de N permutations pour le tableau tabparcours (ou LUT)

[khayyam90]

merci bien