Write an algorithm for faster combinatorics

Question

I am trying to write a combinatorics algorithm to get all possible combinations of k from n without repetition.

Formula:

 n!/(k!(nk)!)); 

Results end with an array. I actually wrote the following:

 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 do this? Is there any way to speed this up? Maybe write it recursively?

Answer 1

This is the fastest I have ever managed to get in the factorial:

 function Factorial($factVal) { if ($factVal < 0) { die("Factorial() Error: Number too small!"); } $factorial = 1; while ($factVal > 1) { $factorial *= $factVal--; } return $factorial ; } 

Answer 2

I think the problem is computing C (n, k), which can be done without calculating the factorial, the trick should first note 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,nk), therefore choose which ever is smaller k or nk 

Feel free to edit if there is an error as I converted it from C and I don't 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 3

IMO should not optimize this if only HEAVY use due to floating point restrictions: 170! = 7.257415615308E + 306, and the following factorial (171!) Is out of the range of the floating point. I assume that recursion will slow down the process (but not verified).

Answer 4

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

This is not true, 0! = 1 0! = 1 defined, so the test should be $x < 0 .

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

You sealed the condition, it should be $xx <= $x .

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

Here you have two potential problems,

• the Factorial function call is slower than the loop calculating the combination counter here
• factorials become very large, so you run the risk of overflow and inaccuracies where you don't need to

Whether these are actual problems depends on your application. You wrote that the results fall into the array, apparently, to avoid recalculation, so the speed for the initial calculation is less important. However, problems with overflow may well be. To avoid this, calculate the array entries recursively on the Pascal 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.

Answer 5

In fact, you do not need to calculate 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 denominator factor overrides the lowest part of the numerator. So, for example, if k> n / 2, all you have to do is multiply the numbers from k + 1 by n and then divide by (nk) !. This saves considerable work on calculating the full factorial.

Here's a draft with 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); }