Write a faster combinatorics algorithm

Question

I'm trying to write a combinatorics algorithm to get all the possible combinations of k out of n without repetitions.

The formula is:

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

The results end up in an array. What I've actually written is this:

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

Is this the fastest way to accomplish this? Is there a way to speed this up? Maybe to write it recursively?

Answer 1

I think the problem is to calculate C(n,k) which can be done without calculating factorial, the trick is to note first that

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

Also for efficiency

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

Feel free to edit if there is a mistake as i have converted it from C and i dont know 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 it is not worth to optimize that unless HEAVY usage, due to float point limitations: 170! = 7.257415615308E+306, and next factorial (171!) is beyond floating point range. I guess that recursion WILL slow down the process (but not tested that).