编写更快的组合数学算法

我认为问题是计算 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

如果有错误，请随意编辑，因为我已将其从 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;
}

IMO 由于浮点限制，除非大量使用，否则不值得优化：170！ = 7.257415615308E+306，下一个阶乘 (171！( 超出浮点范围。我想递归会减慢这个过程(但没有测试过(。

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!，从而为更广泛的数字范围提供准确的结果。

这是我设法获得阶乘循环的最快方法：

function Factorial($factVal) {
    if ($factVal < 0) {
        die("Factorial() Error: Number too small!");
    }
    $factorial = 1;
    while ($factVal > 1) {
        $factorial *= $factVal--;
    }
    return $factorial ;
}

您实际上不需要计算完整的分子和分母。例如：

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