Discussion :

[mazertys17]

Bonjour.

J'aimerai l'avis d'experts en algo/mathématique à propos de la conception d'un générateur de grilles de bingo.
Il est trés facile de générer une suite de grille, de plaques de grilles avec des nombres aléatoires.

Mais il faut que, face à une suite aléatoire de nombres de 0 à 90, il y ait le moins de doublons possible, y compris avec des suite de 10 000 grilles ou + par exemple.

Pour rappel une grille de bingo ressemble à ça :

Code :

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

1
2
3
4
5
 
 
[1, 0, 0, 34, 47, 0, 0, 77, 81],
[0, 12, 0, 42, 58, 0, 74, 82],
[8, 0, 21, 33, 47, 0, 63, 0, 85],

le but est de compléter la grille en fonction des numéros tirés, et enfonction du jeu, on gagne si on complète une ligne, 2 lignes ou la totalité de la grille.
Sachant que des milliers de joueurs peuvent jouer en même temps.

Le but est donc de s'assurer qu'il n'y ai pas 2 joueurs qui gagnent en même temps.

Question bête : est-ce seulement possible ?
Il semblerait que non : le nombre de probablité est vertigineux et il y aura inévitablement quelques doublons au moins.

Question qui nous intéresse ?
Peut ont toutefois optimiser la conception des grilles aléatoire pour faire en sorte qu'il y ait le moins de doublons possible ?
Et si oui, comment ?

J'ai cherché des petites combines mais globalement je pense qu'il faut des compétences et compréhensions mathématiques plus poussées pour répondre vraiment à cette question.


Merci donc au petit géni qui pourra m'éclairer sur cette question !

[Flodelarab]

Bonjour

Mazertys17, tu regardes trop les grilles et pas assez le tirage. En effet, le tirage est un ordre parmi 100 numéros (soit 100! = factorielle de 100), et à chaque tour on consomme un numéro de la liste triée. Ce que tu souhaites est de n'avoir qu'un gagnant à chaque tour (en oubliant les premiers tours pour lesquels trop peu de numéros ont été tirés). Plus le temps s'écoule et plus tu as de gagnants virtuels (seul le premier compte, évidemment). Donc avec 100 numéros, 9 numéros par grille, tu peux avoir 92 tours gagnants maximum, donc 92 gagnants uniques. Avec 10000 grilles, malaise : doublons à foison.

une suite aléatoire de nombres de 0 à 90

Pourtant tu obtiens 98. 92 et 0.

[mazertys17]

Flodelarab Merci pour ta réponse.

En effet...sachant qu'en plus, j'ai oublié de le préciser, on ne peut pas intervenir sur le tirage en lui même. Il doit être totalement aléatoire : le tirage est externe au programme.

Pourtant tu obtiens 98. 92 et 0.

Oui en effet je me suis trompé j'ai sauté la dizaine je vais réctifier ça.

Donc en somme tu pense qu'il est impossible d'empêcher les doublons OU MEME de contrôler les probabilités afin d'en avoir le moins possible ?

[valentin03]

Flodelarab Merci pour ta réponse.

En effet...sachant qu'en plus, j'ai oublié de le préciser, on ne peut pas intervenir sur le tirage en lui même. Il doit être totalement aléatoire : le tirage est externe au programme.

Oui en effet je me suis trompé j'ai sauté la dizaine je vais réctifier ça.

Donc en somme tu pense qu'il est impossible d'empêcher les doublons OU MEME de contrôler les probabilités afin d'en avoir le moins possible ?

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus il y a de générations et plus ça prend de temps.

[mazertys17]

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus y en a et plus ça prend de temps.

Sans doute...mais comment ?

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.
Rien que ça donne mal à la tête...même avec un bon PC de gamer ça doit prendre un certain temps de faire tous les calculs de combinaison...
Sachant qu'on ajoute à ça une puissance 15 de la grille bingo.

Ca fait beaucoup. Au final, à moins, peut être, de ne pas vraiment générer les nombre aléatoirement, ce que j'ai essayé d'imaginer, c'est mission impossible...en tout cas pour quelqu'un comme moi qui n'a pas les maths dans la peau.

[mazertys17]

Y a toujours moyen de supprimer les doublons après génération ou de les empêcher à la génération, mais comme de toutes façons on ne peut faire que par comparaison avec les précédents, plus y en a et plus ça prend de temps.

Sans doute...mais comment ?

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.
Rien que ça donne mal à la tête...même avec un bon PC de gamer ça doit prendre un certain temps de faire tous les calculs de combinaison...
Sachant qu'on ajoute à ça une puissance 15 de la grille bingo.

Ca fait beaucoup. Au final, à moins, peut être, de ne pas vraiment générer les nombre aléatoirement, ce que j'ai essayé d'imaginer, c'est mission impossible...en tout cas pour quelqu'un comme moi qui n'a pas les maths dans la peau.

Et en plus a supposer qu'on mette l'algo sur le papier est-ce qu'on risque pas de rester bloqué à un moment ou l'autre ?

[Flodelarab]

Si on calcule ne serait ce que les probabilités sur un tirage de 90 : c'est donc 90 puissance 90 si je ne m'abuse.

Oui tu t'abuses. Je t'ai déjà dit que c'était 90! (factorielle de 90). Il y a 90! tirages possibles, soit 1.485716e+138 possibilités. Mais cela n'a pas vraiment de rapport avec le fait de répartir les gagnants.