Déterminer la fréquence des nombres apparaissant dans les jets de dés
https://stackoverflow.com/questions/493239
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Pour un jeu, j'essaie de déterminer la fréquence à laquelle un certain nombre apparaîtra à un nombre donné de dés lancés. Je sais ... cette question semble étrange. Laissez-moi essayer de l'expliquer avec des nombres réels.
Donc, pour 1 dé, la fréquence de chaque nombre sera identique. 1-6 s'afficheront un nombre égal de fois.
Maintenant pour 2 dés, les choses deviennent différentes. J'imagine que 5,6,7 seront les plus fréquemment lancés, alors que les nombres aux deux extrémités du spectre seront moins visibles ou pas du tout (dans le cas de 1). Je voudrais savoir comment calculer cette liste et la montrer dans le bon ordre, du plus fréquent au moins fréquent.
Avez-vous des idées?
@duffymo - Ce serait vraiment bien d’avoir une sorte d’algorithme pour le trouver. Il semble que la méthode ci-dessus va nécessiter beaucoup de choix manuel et de placement des chiffres. Si mon nombre de dés est dynamique jusqu'à dire 10, le faire à la main sera inefficace et gênant, à mon avis. :)
La solution
Brouillon d'une manière récursive de le faire:
public static IEnumerable<KeyValuePair<int, int>> GetFrequenciesByOutcome(int nDice, int nSides)
{
int maxOutcome = (nDice * nSides);
Dictionary<int, int> outcomeCounts = new Dictionary<int, int>();
for(int i = 0; i <= maxOutcome; i++)
outcomeCounts[i] = 0;
foreach(int possibleOutcome in GetAllOutcomes(0, nDice, nSides))
outcomeCounts[possibleOutcome] = outcomeCounts[possibleOutcome] + 1;
return outcomeCounts.Where(kvp => kvp.Value > 0);
}
private static IEnumerable<int> GetAllOutcomes(int currentTotal, int nDice, int nSides)
{
if (nDice == 0) yield return currentTotal;
else
{
for (int i = 1; i <= nSides; i++)
foreach(int outcome in GetAllOutcomes(currentTotal + i, nDice - 1, nSides))
yield return outcome;
}
}
À moins que je ne me trompe, cela devrait recracher KeyValuePairs organisé comme [clé, fréquence].
EDIT : À titre d'information, après avoir exécuté cela, les fréquences pour GetFrequenciesByOutcome (2, 6) sont:
2: 1
3: 2
4: 3
5: 4
6: 5
7: 6
8: 5
9: 4
10: 3
11: 2
12: 1
Autres conseils
Il y a 6 * 6 = 36 combinaisons pour deux dés.
2 = 1 + 1 ne peut apparaître qu'une seule fois, sa fréquence est donc 1/36. 3 = 1 + 2 ou 2 + 1, sa fréquence est donc 2/36 = 1/18. 4 = 1 + 3, 2 + 2 ou 3 + 1, sa fréquence est donc 3/36 = 1/12.
Vous pouvez faire le reste jusqu'à douze.
Tout joueur de backgammon le sait bien.
Il n'y a pas de véritable " algorithme " ou une simulation nécessaire - il s’agit d’un simple calcul basé sur une formule de De Moivre:
http://www.mathpages.com/home/kmath093.htm
Et ce n'est pas une " courbe en cloche & "; ou distribution normale.
Additionnez le tableau de fréquences des lancers précédents, le «numéro du côté» en déplaçant sa position, vous obtiendrez le tableau de fréquences que chaque nombre affiche.
1, 1, 1, 1, 1, 1 # 6 sides, 1 roll
1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1
+ 1, 1, 1, 1, 1, 1
_______________________________
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 # 6 sides, 2 rolls
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
+ 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1
______________________________________________
1, 3, 6,10,15,21,25,27,27,25,21,15,10, 6, 3, 1 # 6 sides, 3 rolls
Ceci est beaucoup plus rapide que la simulation en force brute, car une équation simple est la meilleure. Voici mon implémentation de python3.
def dice_frequency(sides:int, rolls:int) -> list:
if rolls == 1:
return [1]*sides
prev = dice_frequency(sides, rolls-1)
return [sum(prev[i-j] for j in range(sides) if 0 <= i-j < len(prev))
for i in range(rolls*(sides-1)+1)]
par exemple,
dice_frequency(6,1) == [1, 1, 1, 1, 1, 1]
dice_frequency(6,2) == [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]
dice_frequency(6,3) == [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1]
Notez que vous devez utiliser "nombre cible - nombre de rôles" comme index de la liste pour obtenir la fréquence de chaque numéro. Si vous souhaitez obtenir des probabilités, utilisez "numéro de côté" ^ "nombre de rôles" comme dénominateur.
sides = 6
rolls = 3
freq = dice_frequency(sides,rolls)
freq_sum = sides**rolls
for target in range(rolls,rolls*sides+1):
index = target-rolls
if 0 <= index < len(freq):
print("%2d : %2d, %f" % (target, freq[index], freq[index]/freq_sum))
else:
print("%2d : %2d, %f" % (target, 0, 0.0))
Ce code est valide
3 : 1, 0.004630
4 : 3, 0.013889
5 : 6, 0.027778
6 : 10, 0.046296
7 : 15, 0.069444
8 : 21, 0.097222
9 : 25, 0.115741
10 : 27, 0.125000
11 : 27, 0.125000
12 : 25, 0.115741
13 : 21, 0.097222
14 : 15, 0.069444
15 : 10, 0.046296
16 : 6, 0.027778
17 : 3, 0.013889
18 : 1, 0.004630
Il y a beaucoup de choses en ligne sur la probabilité de dés. Voici un lien qui m'a aidé avec une question du projet Euler:
Naïf factoïde ...
Saviez-vous que le triangle de Pascal est la distribution de probabilité des sommes des dés N à 2 faces?
1 1 - 1 die, 1 chance at 1, 1 chance at 2
1 2 1 - 2 dice, 1 chance at 2, 2 chances at 3, 1 chance at 4
1 3 3 1 - 3 dice, 1 chance at 3, 3 chances at 4, 3 chances at 5, 1 chance at 6
1 4 6 4 1 - etc.
Implémentation JavaScript à l'aide de la création de fonctions dynamiques:
<script>
var f;
function prob(dice, value)
{
var f_s = 'f = function(dice, value) {var occur = 0; var a = [];';
for (x = 0; x < dice; x++)
{
f_s += 'for (a[' + x + '] = 1; a[' + x + '] <= 6; a[' + x + ']++) {';
}
f_s += 'if (eval(a.join(\'+\')) == value) {occur++;}';
for (x = 0; x < dice; x++)
{
f_s += '}';
}
f_s += 'return occur;}';
eval(f_s);
var occ = f(dice, value);
return [occ, occ + '/' + Math.pow(6, dice), occ / Math.pow(6, dice)];
};
alert(prob(2, 12)); // 2 die, seeking 12
// returns array [1, 1/36, 0.027777777777777776]
</script>
MODIFIER: Plutôt déçu, personne ne l'a signalé. devait remplacer 6 * dice par Math.pow(6, dice). Plus d'erreurs comme ça ...
Il semble y avoir un mystère entourant exactement & "pourquoi &"; c'est, et bien que duffymo en ait expliqué une partie, je suis en train de regarder un autre post qui dit:
Il ne devrait y avoir aucune raison pour que 5, 6 et 7 soient lancés plus [que 2] puisque le premier lancer du dé est un événement indépendant du deuxième jet du dé et que les deux ont une probabilité égale de 1 6 d'être roulé.
Cela a un certain attrait. Mais c'est inexact ... parce que le premier lancer affecte les chances. Le raisonnement peut probablement être fait très facilement à travers un exemple.
Disons que j'essaie de déterminer si la probabilité de lancer 2 ou 7 est plus probable avec deux dés. Si je lance le premier dé et obtient un 3, quelles sont mes chances de lancer un total de 7? Évidemment, 1 sur 6. Quelles sont mes chances d'obtenir un total de 2? 0 sur 6 ... parce que je ne peux rien lancer sur le deuxième dé pour que mon total soit 2.
Pour cette raison, 7 est très (le plus) susceptible d'être lancé ... car peu importe ce que je lance sur le premier dé, je peux toujours atteindre le total correct en lançant le nombre correct sur le deuxième dé. 6 et 8 sont également légèrement moins susceptibles, 5 et 9 plus encore, et ainsi de suite, jusqu'à atteindre 2 et 12, également improbables à 1 chance sur 36 chacune.
Si vous tracez cela (somme vs probabilité), vous obtiendrez une belle courbe en cloche (ou, plus précisément, une approximation en bloc de celle-ci en raison de la nature discrète de votre expérience).
Après de nombreuses recherches sur Internet et un stackoverflow, j'ai trouvé Dr. Math l'explique bien dans une fonction fonctionnelle (un lien dans une autre réponse a une formule incorrecte). J'ai converti la formule de Dr. Math en C # et mes tests nUnit (qui échouaient auparavant avec d'autres tentatives de code) ont tous passé.
J'ai d'abord dû écrire quelques fonctions d'aide:
public static int Factorial(this int x)
{
if (x < 0)
{
throw new ArgumentOutOfRangeException("Factorial is undefined on negative numbers");
}
return x <= 1 ? 1 : x * (x-1).Factorial();
}
En raison de la méthode choisie en mathématiques, j’ai réalisé que je pouvais réduire les calculs si j’avais une fonction factorielle surchargée avec une limite inférieure. Cette fonction peut être annulée lorsque la limite inférieure est atteinte.
public static int Factorial(this int x, int lower)
{
if (x < 0)
{
throw new ArgumentOutOfRangeException("Factorial is undefined on negative numbers");
}
if ((x <= 1) || (x <= lower))
{
return 1;
}
else
{
return x * (x - 1).Factorial(lower);
}
}
public static int Choose(this int n, int r)
{
return (int)((double)(n.Factorial(Math.Max(n - r, r))) / ((Math.Min(n - r, r)).Factorial()));
}
Quand ceux-ci étaient en place, j'ai pu écrire
public static int WaysToGivenSum(int total, int numDice, int sides)
{
int ways = 0;
int upper = (total - numDice) / sides; //we stop on the largest integer less than or equal to this
for (int r = 0; r <= upper; r++)
{
int posNeg = Convert.ToInt32(Math.Pow(-1.0, r)); //even times through the loop are added while odd times through are subtracted
int top = total - (r * sides) - 1;
ways += (posNeg * numDice.Choose(r) * top.Choose(numDice - 1));
}
return ways;
}
