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?

You have an error in your first if block. This is why it is always a good idea to properly space your code out. :) — Jared Farrish
– Jared Farrish, Commented Dec 27, 2011 at 23:37
What array are you constructing? If you are making multiple calls to the combinations function, knowledge of those calls would make it much easier to help you optimize. — templatetypedef
– templatetypedef, Commented Dec 27, 2011 at 23:56

FUD · Accepted Answer · 2011-12-28 04:52:19Z

6

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

answered Dec 28, 2011 at 4:52

FUD

5,2147 gold badges42 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Andrzej Bort · Accepted Answer · 2011-12-27 23:54:13Z

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).

answered Dec 27, 2011 at 23:54

Andrzej Bort

211 bronze badge

Comments

Daniel Fischer · Accepted Answer · 2011-12-28 00:42:39Z

function Factorial($x)
{
    if ($x < 1)
    {
        echo "Factorial() Error: Number too small!";
    }

That's wrong, 0! = 1 is defined, so the test should be $x < 0.

    $ans = 1;
    for ($xx = 2; $xx >= $x; $xx++)

You typo'ed the condition, it must be $xx <= $x.

function Combination($selectcount,$availablecount)
{
    $ans = Factorial($availablecount) / (
        Factorial($availablecount - $selectcount) * Factorial($selectcount)
    );

    return ($ans);
}

You have two potential problems here,

calling the Factorial function is slower than having the loop calculating the combination count here
the factorials become large very quickly, so you risk overflow and inaccuracies where you needn't

Whether these are actual problems depends on your application. You wrote that the results end up in an array, presumably to avoid recalculation, so the speed for the initial calculation is less important. However, the overflow problems may well be. To avoid those, calculate the array entries recursively per Pascal's triangle, choose(n+1,k) = choose(n,k) + choose(n,k-1), where choose(n,k) = 0 if k < 0 or k > n. Alternatively, you can calculate each row starting with choose(n,0) = 1 and choose(n,k) = choose(n,k-1)*(n+1-k)/k for 1 <= k <= n. Both methods avoid the large intermediate n! and thus give accurate results for a wider range of numbers.

Mark Baker · Accepted Answer · 2011-12-27 23:50:38Z

1

This is the fastest I've ever managed to get a factorial loop:

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

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

answered Dec 27, 2011 at 23:50

Mark Baker

213k34 gold badges354 silver badges390 bronze badges

Comments

Ted Hopp · Accepted Answer · 2011-12-28 02:12:59Z

You don't actually need to compute the full numerator and denominator. For instance:

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

That is, the largest factor in the denominator cancels the lowest part of the numerator's factorial. So, for instance, if k > n/2, all you need to do is multiply the numbers from k+1 through n and then divide by (n-k)!. This saves considerable work over computing the full factorial.

Here's a draft at this approach:

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

Collectives™ on Stack Overflow

Write a faster combinatorics algorithm

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related