Allegro.cc Forums » Programming Questions » Equation to get the probability of n dice roll's value

 Elias Member #358 May 2000 Ha, that's the kind of problem they'd have you solve at a Google tech interview!Instead of figuring out very complex math, you can just enumerate over all possibilities. This would solve your specific example with 3 dice with 4 sides: ```count[13] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; for (dice1 = 1; dice1 <= 4; dice1++) { for (dice2 = 1; dice2 <= 4; dice2++) { for (dice3 = 1; dice3 <= 4; dice3++) { sum = dice1 + dice2 + dice3; count[sum]++; } } } ``` To code a loop of an arbitrary number of loops, you can use a trick where you have an array of counters: ```int dice[NUMBER_OF_DIE]; while (true) { int sum = 0; for (int j = 0; j < NUMBER_OF_DIE; j++) { sum += dice[j]; } count[sum]++; for (int j = 0; j < NUMBER_OF_DIE; j++) { dice[j]++; if (dice[j] <= SIDES_OF_DIE) break; dice[j] = 1; } } ``` Basically instead of dice1, dice2, dice3 I use dice[0], dice[1], dice[2] but it works with an arbitrary number.Putting it all together:#SelectExpand 1int dice[NUMBER_OF_DIE]; 2for (int j = 0; j < NUMBER_OF_DIE; j++) dice[j] = 1; 3 4int index = 0; 5int possibilities = pow(SIDES_OF_DIE, NUMBER_OF_DIE); 6int maximum = SIDES_OF_DIE * NUMBER_OF_DIE; 7 8int count[maximum + 1]; 9for (int i = 0; i < maximum + 1; i++) count[i] = 0; 10 11for (int i = 0; i < possibilities; i++) { 12 13 int sum = 0; 14 for (int j = 0; j < NUMBER_OF_DIE; j++) { 15 sum += dice[j]; 16 } 17 count[sum]++; 18 19 for (int j = 0; j < NUMBER_OF_DIE; j++) { 20 dice[j]++; 21 if (dice[j] <= SIDES_OF_DIE) break; 22 dice[j] = 1; 23 } 24} 25 26for (int i = 0; i < maximum + 1; i++) { 27 printf("probability of %d is %f\n", i, count[i] / (double)possibilities); 28} --"Either help out or stop whining" - Evert
 SiegeLord Member #7,827 October 2006 The function that returns a probability of an event (an example of an event would be "die fell with 6 dots on top") is called the probability mass function (PMF). When you have two PMFs whose events are integers, the PMF of the sum of those two integers is the convolution of the two PMFs. You can read about convolutions all over the place, it's a very useful operation and happens to be easy to implement.```std::vector convolve_discrete(const std::vector& pmf1, const std::vector& pmf2) { std::vector ret(pmf1.size() + pmf2.size() - 1, 0.0); for (int i = 0; i < pmf1.size(); i++) for (int j = 0; j < pmf2.size(); j++) ret[i + j] += pmf1[i] * pmf2[j]; return ret; } ``` Note that that function assumes that the integers for each PMF go from 0 to its length - 1. So, for your dice what you do is you pick two dice (whose PMFs are presumably uniform), and use this function to return the PMF of their sum. If you have more dice, then you apply this function recursively.The advantage of this method over enumeration methods is that it supports biased dice easily, variable number of sides per dice etc. It is also a lot faster than enumeration (this method is O(NK^2 log N), I think, and enumeration is O(K^N) where K is number of sides, and N is the number of dice. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]