Tirage Aléatoire avec ponderation en %age

[Argorate]

Bonjour,

j'aurais aimé avoir un avis exterieur sur la meilleur methode algorithmique à suivre pour faire ça:
J'ai un tirage aléatoire à faire avec x cas possible, sachant que le tirage n'est pas équiprobable, j'ai donc pour chaque x, une pondération exprimé en pourcentage qui exprime les chances de tirage de x.

Comme implémenter la chose?

J'avais pensé a deux choses:

la première et de faire un mt_rand(1, 100);
et de découper les pourcentages en tranche.

Exemple :

CAS_POSSIBLE = array(a, b ,c, d);
PONDERATION = array(40, 20, 30, 10);

je peux dire:
si le tirage < 40 j'obtiens a
si tirrage >= 40 && < 60 j'obtiens b
si tirrage >= 60 && < 90 j'obtiens c
et tirrage >= 90 j'obtiens d

mais ça implique donc un petit calcule pour que les if soit générique et pas en dur.

--------------------------------------------------------------------------------

La seconde methode pourait etre de faire des boucle pour remplir un tableau avec les CAS_POSSIBLE, qui apparaitrait PONDERATION fois chacun et de faire un array_rand sur le tout.
C'est plus rapidement expliquer que la première mais je pense que c'est plus couteux comme méthode non?

--------------------------------------------------------------------------------

EDIT: j'ai trouvé sur le net une autre methode très interessante:

$tirage = mt_rand(1,100);
$somme = 0;
$i=0;
while($somme <= $tirage)
{
$somme += $PONDERATION[$i];
if($somme <= $tirage) $i++;
}

et le resultat serait $CAS_POSSIBLE[$i];


Si vous avez d'autres idées je vous écoute, et dans tout les cas, quel methode vosu semble la meilleur dans celles évoquées?

Merci.

[Thêta Tau Tau]

Les 3 cas que tu proposent se rejoignent en fait. Si tu veut pas coder en dur le bout de code que tu as mis est la bonne solution, avec peut être deux trois ajouts si besoin (vérification que la somme fait bien 100 par ex, classement en ordre décroissant pour optimiser, le tout dans une classe...).

Par contre si tu fait beaucoup de tirages en même temps, pour une question de performances il vaut mieux utiliser une loi de probabilité qui te donnera directement le nombre de a, b, c et d sans avoir à faire les tirages un par un.

[Ter Rowan]

je me demande si il y a pas une fonction php acceptant en paramètre un tableau (ou deux), qui tire aléatoirement un élément du dit tableau, en fonction de valeurs associées

mais pas le temps de creuser

[Argorate]

Elle se rejoingne forcement puisque ça donne le resultat, mais la quel est la plus facile a mettre en place & optimisé, d'apres toi?

Sinon je n'est pas compris l'optimisation "classement en ordre décroissant", de quoi parles-tu, que tu veuilles l'ordonner?

PS: il est necessaire dans mon cas que les tirages se fasse bien un par un, les tirages influ sur les suivants...

EDIT: si y a une fonction native qui fait ça se serait super chouette^^

Quelqu'un en a entendu parler?

[ToraTora]

array_rand

http://ca.php.net/manual/fr/function.array-rand.php

[Thêta Tau Tau]

De ce que j'ai compris la fonction array_rand ne permet pas la pondération, donc ce n'est pas vraiment ce qu'il recherche.

L'histoire du classement en ordre décroissant est assez simple en fait :
imaginons que tu ai comme pondération :
a : 10
b : 20
c : 30
d : 40
Si tu fait dans cet ordre tu auras 10% de chances de t'arrêter au premier passage de la boucle while, 20% au 2ème passage...
En commençant par d tu auras 40% de t'arrêter au premier passage puis 30% au 2ème etc. Donc ça optimise un peu.
Bien sur ça n'a d’intérêt que si tu tire beaucoup de fois avec les mêmes paramètres (et dans ce cas les lois de probas sont souvent meilleures, sauf cas particuliers).

[Myrina]

il me semble que les valeurs représentent plutôt des intervalles, comme tu le présentes, il faudrait un tableau:

a : 0
b : 10 => intervalle de a
c : 30 (10+20) => intervalle de a + intervalle de b
d : 60 (10+20+30) => intervalle de a + intervalle de b + intervalle de c

Avec un parcours du tableau tant que la valeur est supérieure à la borne: on boucle.
A la sortie, le cas possible correspond à celui de la borne que tu viens de dépasser.

EDIT: petit script reprenant ce fonctionnement:

$cas=array('a','b','c','d');

$pond=array(40,20,30,10);



//Création du tableau de lecture; transformation des pondérations en borne max

$tab=array();

$nb=count($cas);

$borne=0;

for ($i=0;$i<$nb;$i++) {

	$tab[]=array('borne' => $borne,'cas' =>$cas[$i]);

	$borne+=$pond[$i];

}



$valeur=rand(1,100);

echo "valeur cherchée :".$valeur;



//Recherche du cas selon la valeur

$castrouve=$tab[$i]['cas'];

for ($i=0;$i<$nb;$i++) {

	if ($valeur<$tab[$i]['borne']) { // < ou <= selon comment il faut considérer la borne

		//sortir de la boucle

		break;

	}

	$castrouve=$tab[$i]['cas'];

}



echo "cas trouvé :".$castrouve;

[popayan]

Pour ton exemple :

CAS_POSSIBLE = array(a, b ,c, d);
PONDERATION = array(40, 20, 30, 10);

pourquoi ne pas faire un random sur un tableau contenant 40 a, 20 b, 30 c et 10 d?

[Argorate]

Alalala... les deux là vous faites fort ^^
Les deux méthodes que vous m'exposé sont respectivement les deux que j'ai énoncé dans mon post
Mais je pense que la troisième que j'ai rajouter en EDIT me semble la plus optimisé non?

[Roworll]

J'utilise pour ma part une méthode assez proche de la 3e.

// Définition du tableau

// La clé de chaque entrée représente son poids

$Val=array(

	20=>'Poids 20',

	30=>'Poids 30',

	10=>'Poids 10',

	60=>'Poids 60' 

);



// Récupération du tableau des clés

$Key=array_keys($Val);



// tirage aléatoire basé sur le total des poids

$rnd=mt_rand(1,array_sum($Key));



// Initialisation des variables pour la boucle

$i=-1;

$sum=0;



// boucle

while($rnd>$sum){

	$sum+=$Key[++$i];

}

//Affichage du résultat

echo 'résultat ('.$rnd.') : '.$Val[$Key[$i]];