寫更快的組合數學算法

Question

我想寫一個組合數學算法得到的k所有可能的組合出來的n沒有重複。

的公式爲：

n!/(k!(n-k)!)); 

結果在一個數組中結束。我實際上寫的是這樣的：

function Factorial($x) 
{ 
    if ($x < 1) 
    { 
     echo "Factorial() Error: Number too small!"; 
    ) 

    $ans = 1; 
    for ($xx = 2; $xx >= $x; $xx++) 
    { 
     $ans = $ans * $xx; 
    } 

    return($ans); 
} 

function Combination($selectcount,$availablecount) 
{ 
    $ans = Factorial($availablecount)/(
     Factorial($availablecount - $selectcount) * Factorial($selectcount) 
    ); 

    return ($ans); 
} 

這是實現這個目標的最快方法嗎？有沒有辦法加快這一點？也許遞歸地寫它？

Answer 1

這是我曾經得到了一個階乘循環速度最快：

function Factorial($factVal) { 
    if ($factVal < 0) { 
     die("Factorial() Error: Number too small!"); 
    } 

    $factorial = 1; 
    while ($factVal > 1) { 
     $factorial *= $factVal--; 
    } 
    return $factorial ; 
} 

Answer 2

IMO這是不值得優化，除非大量使用，由於浮點限制：170！ = 7.257415615308E + 306，下一個階乘（171！）超出浮點範圍。 我想遞歸會減慢這個過程（但沒有測試過）。

Answer 3

function Factorial($x) 
{ 
    if ($x < 1) 
    { 
     echo "Factorial() Error: Number too small!"; 
    } 

這是不對的，0! = 1定義，所以測試應該是$x < 0。

$ans = 1; 
    for ($xx = 2; $xx >= $x; $xx++) 

您輸入條件，它必須是$xx <= $x。

function Combination($selectcount,$availablecount) 
{ 
    $ans = Factorial($availablecount)/(
     Factorial($availablecount - $selectcount) * Factorial($selectcount) 
    ); 

    return ($ans); 
} 

您這裏有兩個潛在的問題，

1. 調用Factorial功能比具有循環計算組合很快這裏算
2. 的階乘變大慢，所以你可能溢出不準確的地方

這些是否是實際問題取決於您的應用程序。你寫道結果最終會出現在一個數組中，可能是爲了避免重新計算，所以初始計算的速度並不重要。但是，溢出問題很可能是。爲了避免這些，每個帕斯卡三角形，choose(n+1,k) = choose(n,k) + choose(n,k-1)，遞歸地計算所述陣列的條目，其中choose(n,k) = 0如果k < 0或k > n。或者，你可以計算出每一行開頭choose(n,0) = 1和choose(n,k) = choose(n,k-1)*(n+1-k)/k爲1 <= k <= n。這兩種方法都避免了大的中間值n!，從而爲更廣泛的數字提供準確的結果。

Answer 4

你實際上並不需要計算完整的分子和分母。例如：

C(7,2) = 7!/(2! * (7-2)!) = 7!/(2! * 5!) = (7 * 6)/(2 * 1) 

也就是說，分母中最大的因子抵消了分子階乘的最低部分。所以，例如，如果k> n/2，你需要做的就是將從k + 1到n的數字相乘，然後除以（n-k）!.這比計算完整階乘節省了大量工作。

下面是這個方法的草稿：

function Combination($selectcount,$availablecount) 
{ 
    $remainder = $availablecount - $selectcount; 
    if ($remainder > $selectcount) { 
     $tmp = $remainder; 
     $remainder = $selectcount; 
     $selectcount = $tmp; 
    } 
    $ans = 1; 
    while ($availablecount > $selectcount) { 
     $ans *= $availablecount; 
     $availablecount--; 
    } 
    while ($remainder > 1) { 
     $ans /= $remainder; 
     $remainder--; 
    } 

    return ($ans); 
} 

Answer 5

我認爲這個問題是計算C（N，K），它可以在不計算階乘做，關鍵​​是首先要注意的是

C(n,k) = (n*(n-1)...(n-k+1))/(1*2*...*k) = (n/1)*(n-1/2)*...(n-k+1/k) 

而且效率

C(n,k) = C(n,n-k), therefore choose which ever is smaller k or n-k 

隨意編輯，如果有一個錯誤，因爲我有CONVER從C的特德它，我不知道的PHP

function nCk($n, $k) 
{ 
    if($n-$k<$k) 
     $k = $n-$k; 
    $ans = 1; 
    for($i=1; $i<=$k; ++$i) 
    { 
     $ans = ($ans*($n-$i+1))/$i; 
    } 
    return $ans; 
}