計算結果發生概率的算法

Question

我正在討論的算法將允許您用x個項目呈現它，每個項目的範圍爲a到b，結果爲y。我希望有一個算法，當它與所描述的值一起呈現時，就會輸出它發生的可能性。

例如，對於兩個死。由於我已經知道他們（由於可能的結果如此之低）。它可以告訴你每一種可能性。

該設置將是類似的。 x = 2 a = 1 b = 6。如果你想知道產生一個2的機會，那麼它只會吐出1/36（或它的浮點值）。如果你把7作爲總和，它會告訴你6.

所以我的問題是，是否有一個簡單的方法來實現這樣的事情通過已經寫入的算法。還是必須通過每一個項目的每一次迭代來獲得每個值的組合總數。

確切的公式也會給你組合，使每個值從1-12。

因此，它會給你一個分配數組與每個索引中的每個組合。如果它是0-12。然後0會有0，1會有0，2會有1.

我覺得這是其他人曾經想要的並且已經完成算法的問題類型。如果任何人有一個簡單的方法來做到這一點，只需循環遍歷每個可能的值將是非常棒的。

我不知道爲什麼我想解決這個問題，但由於某種原因，今天我只是有這種想要解決它的感覺。因爲我一直在使用谷歌搜索，並使用wolfram alpha，並且自己嘗試。我認爲是時候承認失敗並問社區。

我想算法是在C，或者也許PHP（即使我寧願它不是因爲它慢得多）。 c的原因僅僅是因爲我想要原始速度，而且我不想處理類或對象。

僞代碼或C是顯示您的算法的最佳方式。

編輯：

而且，如果我冒犯了，在他的名字「B」的人由於對數學的我很抱歉的事。既然我不是故意冒犯的，但我只想說我不理解它。但答案可能留在那裏，因爲我確信有人可能會提出這個問題並理解其背後的數學。

另外我不能決定我想要編碼的方式。我想我會嘗試使用兩者，然後決定哪一個我更喜歡在我的小型圖書館中看到/使用。

我忘了說的最後一件事情是，微積分大概是四年前的事。我對概率，統計和隨機性的理解來自我自己的學習，通過查看代碼/閱讀維基百科/閱讀書籍。

如果有人好奇是什麼引發了這個問題。我有一本書，我正在推遲閱讀Drunkards Walk，然後當我說XKCD 904時，我決定是時候終於開始閱讀了。然後兩個晚上，當我正要睡覺的時候......我曾經想過如何通過簡單的算法解決這個問題，並能夠想到一個。

我對代碼的理解來自於對其他程序的修補，看看我什麼時候發生了什麼事情，然後嘗試自己的事情，同時查看構建函數的文檔。我明白從維基百科上讀取大O符號（儘可能多），而僞代碼是因爲它與python非常相似。我自己，不能寫僞碼（或者說大學裏的老師說）。我不斷收到像「讓它更像真實代碼使其更像僞代碼」的筆記。那件事沒有改變。

編輯2：成爲任何人搜索這個問題只是很快就想要的代碼。我已經將它包含在下面。它在LGPLv3下獲得許可，因爲我確信存在此代碼的封閉源代碼。

它應該是相當便攜的，因爲它完全由c寫成。如果有人想把它用c語言編寫成各種語言的擴展，那麼這樣做應該花費很少的精力。我選擇「標記」第一個與「請求數學博士」相關聯的答案作爲答案，因爲這是我用於此問題的實現。

的第一個文件的名稱是「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, 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; 
} 

這裏是展示實施正如我在以前的文件中說，該文件。

#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)); 
} 

Answer 1

首先，您不必擔心範圍從a到b。您只需從y中減去a*x，然後假設範圍從0到b-a。 （因爲每個項目貢獻至少a的總和......所以，你可以在a一次爲每個x項減去了。）

其次，注意你真正要做的是計數的實現特定總和的方法數量。計數除以簡單的指數(b-a+1)^x即可。

此問題已被覆蓋「問數學博士」圍繞一個十年前：

http://mathforum.org/library/drmath/view/52207.html

他的公式假設編號從1到X，於是就用他的回答骰子，你可能想將您的範圍移動a-1（而不是a）將其轉換爲該形式。

他的派生使用生成函數，我覺得值得一點解釋。這個想法是定義一個多項式f(z)，這樣係數就是z^n滾動方式的數量n。對於單六面模，例如，這是生成函數：

z + z^2 + z^3 + z^4 + z^5 + z^6 

- 因爲軋製從1每個數字至6之一的方法，滾動別的的零分的方式。

現在，如果你有兩個發電功能g(z)和h(z)兩套骰子，事實證明這些集合的並集的生成函數是g和h只是產品。 （盯在了「乘兩個多項式」操作了一段時間說服自己這是真的。）例如，對於兩個骰子，我們只要平方以上表達式獲得：

z^2 + 2z^3 + 3z^4 +4z^5 + 5z^6 + 6z^7 + 5z^8 + 4z^9 + 3z^10 + 2z^11 + z^12 

通知我們如何閱讀直接關閉係數的組合數量：1個方法得到2個（1*z^2），6個方法得到7個（6*z^7）等

表達式的立方體會給我們三個骰子的生成函數;第四力量，四個骰子;等等。

當您以封閉形式編寫生成函數時，此公式的威力來自於乘法，然後使用Binomial Theorem再次展開它們。我按照Math博士對細節的解釋。

Answer 2

要獲得所有的可能性，你可以讓地圖值的：

for (i=a to b) { 
for (j=a to b) { 
    map.put(i+j, 1+map.get(i+j)) 
} 
} 

爲了更有效的方式來算的款項，您可以使用模式 6 7的，5個6的，4 5點的，3 4，2 3，1兩個。

該模式對於n×n網格保持，將會有n（n + 1）個，總和1大於或小於1的可能性較小。

這將計數可能性，例如Count（6,1/2/3/4/5/6）將給出骰子總和的可能性。

import math 
def Count(poss,sumto): 
    return poss - math.fabs(sumto-(poss+1)); 

編輯：在C這將是：

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h>; 

int count(int poss, int sumto) 
{ 
    return poss - abs(sumto-(poss+1)); 
} 

int main(int argc, char** argv) { 
    printf("With two dice,\n"); 
    int i; 
    for (i=1; i<= 13; i++) 
    { 
     printf("%d ways to sum to %d\n",count(6,i),i); 
    } 
    return (EXIT_SUCCESS); 
} 

給出：

With two dice, 
0 ways to sum to 1 
1 ways to sum to 2 
2 ways to sum to 3 
3 ways to sum to 4 
4 ways to sum to 5 
5 ways to sum to 6 
6 ways to sum to 7 
5 ways to sum to 8 
4 ways to sum to 9 
3 ways to sum to 10 
2 ways to sum to 11 
1 ways to sum to 12 
0 ways to sum to 13 

Answer 3

數論，統計和組合導致你相信，在爲一個數值到達事件的概率 - 你必須知道2件事：

• 可能結果的數量
• 在總體結果集內有多少個數等於您尋求概率值的結果'y'。

在僞代碼：

numPossibleOutcomes = calcNumOutcomes(x, a, b); 
numSpecificOutcomes = calcSpecificOutcome(y); 
probabilityOfOutcome = numSpecificOutcomes/numPossibleOutcomes; 

然後，只需編碼了2個功能，高於該應該很容易。

Answer 4

比方說，f(a, b, n, x)代表您可以選擇a和b之間的n個數字的方法數量，它們總計爲x。

然後發現：

f(a, b, n, x) = f(0, b-a, n, x-n*a) 

事實上，只需要實現從每個n個數的X之和，減去一個方式，那麼總和將成爲x - n*a和他們每個人將介於0到ba之間。

因此，只需編寫代碼即可找到f(0, m, n, x)。

現在注意的是，所有的方式來實現這一目標，使得最後一個號碼是c爲：

f(0, m, n-1, x-c) 

事實上，我們有N-1號離開，並希望總和爲x-C。 然後我們有一個遞推公式：

f(0,m,n,x) = f(0,m,n-1,x) + f(0,m,n-1,x-1) + ... + f(0,m,n-1,x-m) 

，其中右邊的加數對應的最後一個數字等於0，1，...，M

現在，您可以實現使用遞歸，但這會太慢。

但是，有一種稱爲memoized遞歸的技巧，即保存函數的結果，以便不必再次計算它（對於相同的參數）。

備份遞歸的複雜度爲O(m * n)，因爲這是您需要計算和保存的不同輸入參數的數量。

一旦你計算了你需要除以總數的posiblity，這是（m + 1）* n得到最終的概率。