Tirage au sort avec poids

Signaler
Messages postés
12
Date d'inscription
lundi 13 mai 2002
Statut
Membre
Dernière intervention
30 octobre 2009
-
Messages postés
3706
Date d'inscription
lundi 5 juillet 2004
Statut
Membre
Dernière intervention
27 avril 2012
-
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.

7 réponses

Messages postés
1044
Date d'inscription
lundi 7 mars 2005
Statut
Membre
Dernière intervention
13 juillet 2010
7
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.
Messages postés
12
Date d'inscription
lundi 13 mai 2002
Statut
Membre
Dernière intervention
30 octobre 2009

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?
Messages postés
1044
Date d'inscription
lundi 7 mars 2005
Statut
Membre
Dernière intervention
13 juillet 2010
7
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.
Messages postés
3706
Date d'inscription
lundi 5 juillet 2004
Statut
Membre
Dernière intervention
27 avril 2012
30
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 :
<?php
$tab[0] = 5;
$tab[1] = 10;
$tab[2] = 100;
$tab[3] = 1000;
$tab[4] = 900;

asort($tab);
$total = array_sum($tab);
$rdNumber = mt_rand(0, $total);
$seek = 0;

foreach($tab as $k=>$v) {
    if ($rdNumber <= $seek+= $v) {
        $resultat = $k;
        break;
    }
}
?>


(pas trop testé, ... à voir)


Cordialement,


Kohntark -
Messages postés
1044
Date d'inscription
lundi 7 mars 2005
Statut
Membre
Dernière intervention
13 juillet 2010
7
$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.
Messages postés
12
Date d'inscription
lundi 13 mai 2002
Statut
Membre
Dernière intervention
30 octobre 2009

@Kohntark : ça sert à quoi de trier le tableau?
Messages postés
3706
Date d'inscription
lundi 5 juillet 2004
Statut
Membre
Dernière intervention
27 avril 2012
30
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 :
<?php
$total = 2015;
$rdNumber = rand() * $total;
// => 47638630
$rdNumber = mt_rand(0, $total);
// => 1670
?>


Cordialement,


Kohntark -