Tirage au sort avec poids

Question

salut à tous,

Je voudrais tirer au sort une personne mais ces personnes ont plus ou moins de chance : 

$tab[1] = 10;
$tab[2] = 100;
$tab[3] = 1000;
$tab[4] = 900;

ce qui veut dire en français , que le joueur 1 a 10 chance de gagner, les joueur 2 a 100 chances, ...

Je ne sais pas comment avantage le joueur 3 dans le tirage.

Merci de votre aide.

Arto_8000 · Answer

La façon la plus simple d'aborder le problème serait d'avoir un algorithme dans ce genre :

<?php
$total = 0;
for ($i=0;$i<count($tab); $i++)
    $total += $tab[$i];

$rdNumber = rand() * $total;
$seek = 0;
$resultat = 0;
for ($i=0; $i<count($tab); $i++) {
    if ($rdNumber <= $seek+$tab[$i]) {
        $resultat = $i;
        break;
    }
    $seek += $tab[$i];
}

echo 'Le résultat gagnant est le ' . $resultat;
?>

En gros ce que l'algorithme fait c'est d'additionner toutes les chances et après on prend le nombre aléatoire qui nous mène vers notre chiffre.

Dans ton cas la sommes est 2010. Si le nombre aléatoire est entre 0 et 10, c'est le 1 qui gagne, entre 10 et 110 c'est le 2 qui gagne, entre 110 et 1110, c'est le 3 qui gagne, etc.

cs_Pekka · Answer

Merci,

J'avais pensé à cette solution mais je trouve qu'une boucle pour faire des additions c'est pas terrible si j'ai beaucoup de joueur.
Qu'est que tu en penses?

Arto_8000 · Answer

La boucle pour les additions c'est à peu près inévitable, car il faut savoir la somme des chances que tout le monde a eu. Tu peux toujours le précalculé et le stocké quelque part pour éviter d'avoir à le faire à chaque tirage, mais tu ne peux pas t'en passer.

Sinon l'algorithme en soi peut être optimisé, mais le principe va reste le même.

kohntark · Answer

Salut, @Arto: J'ai peut être loupé quelque chose mais je doute que ton code fonctionne, ne serait ce que par le "$rdNumber = rand() * $total;" Me tromperai je ? J'aurai plutôt fait ça : $v) { if ($rdNumber <= $seek+= $v) { $resultat = $k; break; } } ?> (pas trop testé, ... à voir) Cordialement, Kohntark -

Arto_8000 · Answer

$rdNumber = rand() * $total;

revient au même que ton

$rdNumber = mt_rand(0, $total);

Pour le reste, l'algorithme est à peu près le même à l'exception que tu utilises plus de fonction native (ce qui est plus performant avec PHP). Ça serait une solution plus performante.

cs_Pekka · Answer

@Kohntark : ça sert à quoi de trier le tableau?

kohntark · Answer

Salut, @Pekka : Il est nécessaire de trier le tableau dans l'ordre croissant car sinon : Pour reprendre ton tableau : $tab[0] = 5; $tab[1] = 10; $tab[2] = 100; $tab[3] = 1000; $tab[4] = 900; Le code va tirer un nombre aléatoire entre 0 et la somme de toutes les valeurs du tableau. Ensuite il parcours chaque élément de ce dernier et regarde si le nombre aléatoire est inférieur au cumul : Joueur 0 0+5 = 5 Joueur 1 5+10 = 15 Joueur 2 15+100 = 115 Joueur 3 115+1000 = 1115 Joueur 4 1115+900 = 2015 Pour un nombre aléatoire de 2000 c'est le joueur 4 qui va gagner, hors ça devrait être le 3 (on ne compare pas sur une plage mais sur l'éloignement de zéro ($seek)) En ordonnant préalablement le tableau : Joueur 0 0+5 5 (2000 > 5> perdu) Joueur 1 5+10 15 (2000 > 15> perdu) Joueur 2 15+100 = 115 ... Joueur 4 115+900 1015 (2000 > 1015> perdu) Joueur 3 1015+1000 2015 ((2000 < 2015> gagné) @Arto : rand retourne un nombre pseudo aléatoire entre 0 et la plus grande valeur possible (dépendante du système), non ? Ainsi : 47638630 $rdNumber = mt_rand(0, $total); // => 1670 ?> Cordialement, Kohntark -

Tirage au sort avec poids

7 réponses

Votre réponse

Discussions similaires