编写更快的组合算法

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

这是最快的完成方式吗？有什么方法可以加速它吗？也许可以递归地编写它？

- Giorgio

---

你的第一个 if 代码块中有错误。因此，适当地对代码进行空格处理总是一个好主意。:) - Jared Farrish

你正在构建哪个数组？如果你要多次调用combinations函数，了解这些调用将使帮助你优化变得更容易。 - templatetypedef

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

- FUD

Answer 2

在没有重度使用的情况下，我认为优化这个内容是不值得的，原因是由于浮点数的限制：170！= 7.257415615308E + 306，而下一个阶乘（171！）超出了浮点范围。我猜递归会减慢这个过程（但没有测试过）。

- Andrzej Bort

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

- Daniel Fischer

Answer 4

这是我最快成功编写的阶乘循环：

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

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

- Mark Baker

Answer 5

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

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

- Ted Hopp