The algorithm I'm talking about using would allow you to present it with x number of items with each having a range of a to b with the result being y. I would like to have an algorithm which would, when presented with the values as described would output the possibility of it happening.
For example, for two die. Since I already know them(due to the possible results being so low). It'd be able to tell you each of the possibilities.
The setup would be something like. x=2 a=1 b=6. If you wanted to know the chance of having it result in a 2. Then it'd simply spit out 1/36(or it's float value). If you put in 7 as the total sum, it'd tell you 6.
So my question is, is there a simple way to implement such a thing via an algorithm that is already written. Or does one have to go through every single iteration of each and every item to get the total number of combinations for each value.
The exact formula would also, give you the combinations to make each of the values from 1-12.
So it'd give you a distribution array with each one's combinations at each of the indexes. If it does 0-12. Then 0 would have 0, 1 would have 0, and 2 would have 1.
I feel like this is the type of problem that someone else has had and wanted to work with and has the algorithm already done. If anyone has an easy way to do this beyond simply just looping through every possible value would be awesome.
I have no idea why I want to have this problem solved, but for some reason today I just had this feeling of wanting to solve it. And since I've been googling, and using wolfram alpha, along with trying it myself. I think it's time to concede defeat and ask the community.
I'd like the algorithm to be in c, or maybe PHP(even though I'd rather it not be since it's a lot slower). The reason for c is simply because I want raw speed, and I don't want to have to deal with classes or objects.
Pseudo code, or C is the best ways show your algorithm.
Edit:
Also, if I offended the person with a 'b' in his name due to the thing about mathematics I'm sorry. Since I didn't mean to offend, but I wanted to just state that I didn't understand it. But the answer could've stayed on there since I'm sure there are people who might come to this question and understand the mathematics behind it.
Also I cannot decide which way that I want to code this up. I think I'll try using both and then decide which one I like more to see/use inside of my little library.
The final thing that I forgot to say is that, calculus is about four going on five years ago. My understanding of probability, statistics, and randomness come from my own learning via looking at code/reading wikipedia/reading books.
If anyone is curious what sparked this question. I had a book that I was putting off reading called The Drunkards Walk and then once I say XKCD 904, I decided it was time to finally get around to reading it. Then two nights ago, whilst I was going to sleep... I had pondered how to solve this question via a simple algorithm and was able to think of one.
My coding understanding of code comes from tinkering with other programs, seeing what happened when I broke something, and then trying my own things whilst looking over the documentation for the build in functions. I do understand big O notation from reading over wikipedia(as much as one can from that), and pseudo code was because it's so similar to python. I myself, cannot write pseudo code(or says the teachers in college). I kept getting notes like "make it less like real code make it more like pseudo code." That thing hasn't changed.
Edit 2: Incase anyone searching for this question just quickly wanted the code. I've included it below. It is licensed under the LGPLv3 since I'm sure that there exists closed-source equivalents of this code.
It should be fairly portable since it is written entirely in c. If one was wanting to make it into an extension in any of the various languages that are written in c, it should take very little effort to do so. I chose to 'mark' the first one that linked to "Ask Dr. Math" as the answer since it was the implementation that I have used for this question.
The first file's name is "sum_probability.c"
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
/*!
* file_name: sum_probability.c
*
* Set of functions to calculate the probabilty of n number of items adding up to s
* with sides x. The question that this program relates to can be found at the url of
* http://stackoverflow.com/questions/6394120/
*
* Copyright 2011-2019, Macarthur Inbody
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the Lesser GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the Lesser GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/lgpl-3.0.html>.
*
* 2011-06-20 06:03:57 PM -0400
*
* These functions work by any input that is provided. For a function demonstrating it.
* Please look at the second source file at the post of the question on stack overflow.
* It also includes an answer for implenting it using recursion if that is your favored
* way of doing it. I personally do not feel comfortable working with recursion so that is
* why I went with the implementation that I have included.
*
*/
/*
* The following functions implement falling factorials so that we can
* do binomial coefficients more quickly.
* Via the following formula.
*
* K
* PROD (n-(k-i))/i
* i=1;
*
*/
//unsigned int return
unsigned int m_product_c( int k, int n){
int i=1;
float result=1;
for(i=1;i<=k;++i){
result=((n-(k-i))/i)*result;
}
return result;
}
//float return
float m_product_cf(float n, float k){
int i=1;
float result=1;
for(i=1;i<=k;++i){
result=((n-(k-i))/i)*result;
}
return result;
}
/*
* The following functions calculates the probability of n items with x sides
* that add up to a value of s. The formula for this is included below.
*
* The formula comes from. http://mathforum.org/library/drmath/view/52207.html
*
*s=sum
*n=number of items
*x=sides
*(s-n)/x
* SUM (-1)^k * C(n,k) * C(s-x*k-1,n-1)
* k=0
*
*/
float chance_calc_single(float min, float max, float amount, float desired_result){
float range=(max-min)+1;
float series=ceil((desired_result-amount)/range);
float i;
--amount;
float chances=0.0;
for(i=0;i<=series;++i){
chances=pow((-1),i)*m_product_cf(amount,i)*m_product_cf(desired_result-(range*i)-1,amount)+chances;
}
return chances;
}
And here is the file that shows the implementation as I said in the previous file.
#include "sum_probability.c"
/*
*
* file_name:test.c
*
* Function showing off the algorithms working. User provides input via a cli
* And it will give you the final result.
*
*/
int main(void){
int amount,min,max,desired_results;
printf("%s","Please enter the amount of items.\n");
scanf("%i",&amount);
printf("%s","Please enter the minimum value allowed.\n");
scanf("%i",&min);
printf("%s","Please enter the maximum value allowed.\n");
scanf("%i",&max);
printf("%s","Please enter the value you wish to have them add up to. \n");
scanf("%i",&desired_results);
printf("The total chances for %i is %f.\n", desired_results, chance_calc_single(min, max, amount, desired_results));
}