编写更快的组合算法

Question

我正在尝试编写一个组合算法，以在不重复的情况下从 n 中获取 k 的所有可能组合。

公式为：

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

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

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. 调用阶乘函数比循环计算组合计数要慢，
2. 阶乘很快就会变大，因此在不需要的地方可能会出现溢出和不准确的风险

。实际问题取决于您的应用程序。您写道，结果最终以数组形式结束，大概是为了避免重新计算，因此初始计算的速度不太重要。然而，溢出问题很可能是存在的。为了避免这些问题，请根据帕斯卡三角形递归计算数组条目，choose(n+1,k) = choice(n,k) + Choose(n,k-1)，其中 choose (n,k) = 0 如果 k 0 或 k > n。或者，您可以从 choose(n,0) = 1 和 choose(n,k) = choice(n,k-1)*(n+1-k) 开始计算每一行)/k 表示 1 <= k <= n。这两种方法都避免了大的中间 n!，因此可以为更广泛的数字提供准确的结果。

Answer 4

这是我获得阶乘循环最快的速度：

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

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

Answer 5

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

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

也就是说，分母中最大的因数抵消了分子阶乘中最低的部分。因此，例如，如果 k > n/2，您所需要做的就是将 k+1 到 n 的数字相乘，然后除以 (nk)!。这节省了计算全阶乘的大量工作。

这是此方法的草案：

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