php - 编写更快的组合算法

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