Selection aléatoire conditionelle (:D) - Page 1

J'ai une liste de 10 elements : {ABC,BDE,AEF,ABE,BCF,CDD,ADE,BCF,ACD,BCD}

Dans cette liste de 10 elements je veux en choisir un au hazard, mais il faut qu'il comporte un 'A'. Certains elements ne doivent pas être selectionnés donc un random(10) ne marche pas.
Est-ce que quelqun aurait une solution à la fois simple et rapide ? Sachant que la liste a une longueur variable et que A est variable également, donc créer une seconde liste des choix valides n'est pas possible (et puis c'est lent).

Autre chose : les solutions bateau du genre "tu refais le random jusqu'à tomber sur un choix qui contient un A" c'est pas bon non plus (un random c'est trop lent je préfere en avoir le moins possible).

Vala

bah y'a la solution de faire un rand N (nb elem dans ta liste) suivi d'un for pour compter le nombre à choisir

si le rand retourne 14 ton parcours de liste se passe ainsi:

{ABC,BDE,AEF,ABE,BCF,CDD,ADE,BCF,ACD,BCD} 
  1 j++  2   3  j++  j++  4  j++ 5   j++
  6  j++  7   8  j++  j++  9  j++ 10  j++
  11  j++ 12 13  j++  j++ 14

à la fin tu prends j modulo la taille de la liste et t'as le rang de ton truc...

J'avais pas bien comprit ce qu'il voulait dire, donc si ça peut servir à quelqun d'autre :

< Vertyos > Vincent_MARCHAND » je comprend pas trop ton truc ?
< Vincent_MARCHAND > 1) tu tire au sort ton nombre
< Vertyos > ahh
< Vertyos > t'avance "rand()" fois en sautant les elements invalides ?
< Vincent_MARCHAND > 2) le nombre obtenu te donne le nième truc contenant un "a" < Vincent_MARCHAND > voilà

Je pense que ce que je vais proposer risque d'être trop long et pas économique:

Tu parcours la liste et tu recherche la lettre A, tu place l'item n° dans une liste de numéro d'items et tu incrémente la variable qui indique le nombre max d'items dans cette liste.

Donc ça donne

int items=0;
int i;
unsigned char lst[10];

for (i=0;i<10;i++) {
if (strchr (ListChar[i],"A")!=NULL) lst[items++]=i;}

Puis il te reste à faire un random sur la liste lst qui te donne un item dans la ListChar.

Vertyos :
Est-ce que quelqun aurait une solution à la fois simple et rapide ? Sachant que la liste a une longueur variable et que A est variable également, donc créer une seconde liste des choix valides n'est pas possible (et puis c'est lent).

Désolé, c'est bien ce que je me disait tu recherche la solution la plus rapide.

Heu oui c'est une fonction qui sera utilisée environ 4 fois par frame, donc à 20fps faut que ça soit rapide

Moi à ta place je coderai ça en C avec une fonction ou ta liste passe en argument.
Et surtout j'esserais de trouver un random bien plus rapide.

4 fois par frame, donc à 20fps faut que ça soit rapide

Dans ce cas il faut une fonction de feu de dieu.

Moi je n'ai toujours pas compris la technique de vince

Geogeo >

Oui c'est codé en C (pour avoir 20fps de toute façon ça pouvait pas être du basic ), et pour gagner en vitesse la première chose c'est de ne pas utiliser de fonction, ça économise déjà l'appel (et comme elle ne serait utilisée que là, ça ne gene pas).

"Du feu de dieu", non pas forcément on est en C quand même... Le systeme de Vince fonctionne, mais si quelqun en trouve un qui ralentisse encore moins...

Pour le random plus rapide ça n'a plus grand chose à voir avec l'algo mais ça m'interesse quand même, si quelqun a

Jackiechan >

cf. le log de #3l33t : "< Vertyos > t'avance "rand()" fois en sautant les elements invalides ?". Je tire un nombre aléatoire N entre 1 et "dimention de la liste", et j'avance N fois dans cette liste en ne m'arretant qu'aux élements selectionables (une fois arrivé en bout de liste je retourne au début).

La technique de vince a un gros problème: les choix ne sont pas équiprobables! Par exemple... (Ah non, c'est un mauvais exemple... J'en cherche un autre.)

Pour avoir des choix équiprobables avec la méthode de vince, il faut connaître le nombre d'éléments valides, c'est-à-dire qu'il faut utiliser la boucle de geogeo, mais on n'a pas besoin de recopier les éléments, juste de les compter. Cela dit, la solution de geogeo est peut-être meilleure, parce que si tu comptes les éléments valides, puis tu appliques la méthode de vince, tu es obligé de faire tous les tests 2 fois.

Bon, déjà, le 14 dans l'exemple de vince est foireux, parce que c'est plus grand que le nombre d'éléments de la liste, c'est-à-dire 10. Mais dans son exemple, les éléments sont équiprobables par pur hasard (parce que le nombre d'éléments valides divise le nombre total d'éléments), donc il nous faut un autre:

{ABC,BDE,AEF,ABE,CDD,ADE,BCF,ACD} (8 éléments, dont 5 valides)
Ici, ABC, AEF et ABE peuvent être choisis de 2 manières chacun, ADE et ACD seulement d'une seule manière. Donc au lieu d'avoir des probabilités 1/5 pour chacun, tu as des probabilités 2/8=1/4 pour les premiers et 1/8 pour ADE et ACD.

la seul methode rapide est de faire un tri bien avant que tu rentres ses info dasn ta table..

Merde, Kevin a été plus rapide que moi.
En effet, la méthode de vince ne permet pas d'équiprobabilité dans les choix.
Et pourquoi tu ne peux pas avoir une seconde liste dans laquelle tu mets les indices des élements de la première liste qui peuvent être choisis et tu fais ton rand dans la deuxième liste ?
Bref, la technique de geogeo, quoi.

Oui mais le problème vient du fait que "A", le critère de selection, est variable. Ça veut dire qu'il est impossible de compter à l'avance le nombre d'élements valides, ni de les sortir une bonne fois pour toute dans une liste.

C'est vrai que le problème de l'équiprobabilité est genant, j'y avait pensé avec une autre solution, qui consistait à prendre un element N aléatoire dans la liste et avancer au prochain element valide suivant N, mais alors la probabilité dépend du nombre d'élements invalides qui séparent les elements valides.

De plus la liste est de longueur variable (elle peut être TRES longue) donc il faudrait logiquement allouer la 2eme liste (celle qui contient que des elements valides) à chaque fois, or 4*20 fois par secondes ça va serieusement ralentir

Bah ce que tu peux faire, c'est par exemple au lieu d'allouer de l'espace pour les N éléments de ta liste, tu alloues de l'espace pour 2N éléments, comme ça c'est plus simple à coder, et tu n'auras besoin de faire des opérations de réallocation que lorsque le nombre d'élément changera. A chaque fois, tu réalloueras 2N*sizeof(élément).
Puis à chaque fois que tu auras besoin de faire ton rand, tu fais le tri (linéaire) qui consiste à vérifier si chaque élément de la liste fait partie de ceux qui seront choisis, et tu les places directement après la liste, dans les N éléments restant.
Et tu fais ton rand dans cette deuxième partie de liste.
Je pense que c'est peu coûteux et c'est totalement équiprobable.
Tu peux éventuellement sauver le type d'élément à chercher pour ne pas avoir à refaire le tri dans le cas où tu chercherais plusieurs fois de suite le même élément.

tu fait un tris ( A, B C ) tout vide au debut du programme c'est possible
apres a l'aide de liste chainé tu complettes tes piles
apres la suite tu la devines. c'est la seule methode rapide et applicable

Oui, mais elle peut demander jusqu'à N*nb_de_critères octets en plus.
Mais c'est vrai que si sa liste est longue, ma méthode (celle de geogeo en fait) risque d'être un peu lente peut-être.

Jackiechan > Heu oui mais la liste d'origine est en fait un tableau de pointeurs vers des structures, donc je ne vais pas en allouer 2 fois plus elle est assez grosse. Ça rejoint l'idée d'une seconde liste et on dirait bien que c'est la seule solution équiprobable

Jackosking > Rien comprit

ha bon?
tu as combien de combiniasion possible?

Mué j'ai pas tout lu mais ce que je ferai c'est un rand(dim de la liste) et avancer jusqu'au prochain élément correct. OK c'est pas équiprobable, mais il s'en faut de peu. Au pire on fait un autre rand pour savoir si on avance ou on recule jusqu'au prochain élément. En bouclant les extrémités bien sûr.

Cette solution approche celle de Vince, donc a les mêmes problèmes :-/

Jackosking > Combinaisons ???

ABC,BDE,AEF,ABE,BCF,CDD,ADE,BCF,ACD,BCD
=> le nombre de triplets possibles?

Ah nan mais ça c'était un exemple. C'est plutot une liste de structures qui aurait un char "valide", et c'est ce char qui est utilisé pour définir un element valide / invalide. Par exemple à une frame, seules les structures dont la variable "valide" vaut 60 sont selectionables, puis à la frame suivante c'est la valeur 156, etc...

Il te reste encore une autre méthode.

Tu applique une fonction de trie à ta liste et tu pose une varaible qui identique ou le trie ce termine dans ta liste, il te reste à faire un rand.

Problème tu doit utiliser encore un for pour trier et encore une liste temporaire et aussi je pense que ça sera plus lent que ma méthode précédente.

Mais la fonction dans ma méthode de faire une liste correcte d'item tu ne l'a fait pas 4 fois par frame. Tu effectue seulement le random donc je trouve que ma solution et la plus rapide dans ce cas puisque la boucle for tu ne la fera que 1 fois par frame?

J'en voit pas d'autre sans utiliser une autre liste et effectuer un minimum d'opération de trie dessus.

Justement les 4 fois par frame sont obligatoirement 4 fois ou le critere de selection sera différent :-/
Pas grave je vais utiliser la solution que je refusais au post #0 et que geogeo a quand même reprit (), c'est à dire une seconde liste. Ça sera plus lent mais équiprobable.

Je vois pas te conseillier d'autre, surtout que tu as l'air de demander énormément de vitesse. Ou tu fait une allocation définitive de la liste temporaire au lancement du prog mais la tu perd de la mémoire et tu gagne de la vitesse. Faut voir.

Bon, j'ai limité le nombre maximum d'elements valides à 256, donc en allouant une seule fois 256 octets, je perd un peu de place mais ça devrait aller suffisement vite.

Merci tlm

Pas de quoi, j'aime bien ce genre de problème car il est utile pour divers cas.

Vertyos
: donc il faudrait logiquement allouer la 2eme liste (celle qui contient que des elements valides) à chaque fois

Tu connais alloca? Ou les tableaux à taille variable du C99? Si c'est l'allocation qui te dérange, voilà la solution.