This is some code I wrote a long time ago as part of the TDAG mailing list. It calculates Factorials, the number of Combinations and Permutations. This is the mathematics, it calculates the number of Combinations and Permutations, it doesn’t create each different Combination and Permutation.

They take Cardinals as parameters because it doesn’t make sense to accept negative numbers. Keep in mind that factorials get big really, really quickly, so if you use too large of numbers then it will overflow even the Int64.

<br /> unit FactCombPerm;</p> <p>interface</p> <p>// Parameters are Cardinal because Int64 isn't Ordinal<br /> // Besides, Factorial(100) will overflow Int64 already.<br /> function Factorial(const ANumber: Cardinal): Int64; overload;<br /> function Factorial(const ANumber: Cardinal;<br /> const AStop: Cardinal): Int64; overload;<br /> function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;<br /> function Combination(const ACount, AChoose: Cardinal): Int64;<br /> function Permutation(const ACount, AChoose: Cardinal): Int64;</p> <p>implementation</p> <p>function Factorial(const ANumber: Cardinal): Int64; overload;<br /> // n! = n * (n-1) . . . n(2)<br /> var<br /> lCtr: Cardinal;<br /> begin<br /> Result := 1;<br /> for lCtr := ANumber downto 2 do<br /> Result := Result * lCtr;<br /> end;</p> <p>function Factorial(const ANumber: Cardinal;<br /> const AStop: Cardinal): Int64; overload;<br /> // Factorial with a stop point (needed in the optimized Combination routine<br /> // if no AStop is specified then is the same as Factorial<br /> var<br /> lCtr: Cardinal;<br /> begin<br /> Result := 1;<br /> if ANumber >= AStop then<br /> for lCtr := ANumber downto AStop do<br /> Result := Result * lCtr;<br /> end;</p> <p>function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;<br /> // n!<br /> // n_C_k = ----------<br /> // k!(n - k)!<br /> begin<br /> if AChoose < ACount then<br /> Result := Factorial(ACount)<br /> div (Factorial(AChoose) * Factorial(ACount - AChoose))<br /> else<br /> Result := 0;<br /> end;</p> <p>function Combination(const ACount, AChoose: Cardinal): Int64;<br /> // n!<br /> // n_C_k = ----------<br /> // k!(n - k)!<br /> // with optimizations even!<br /> begin<br /> if AChoose < ACount then<br /> Result := Factorial(ACount, succ(ACount - AChoose))<br /> div (Factorial(AChoose))<br /> else<br /> Result := 0;<br /> end;</p> <p>function Permutation(const ACount, AChoose: Cardinal): Int64;<br /> // n!<br /> // n_P_k = --------<br /> // (n - k)!<br /> begin<br /> if AChoose < ACount then<br /> Result := Factorial(ACount)<br /> div Factorial(ACount - AChoose)<br /> else<br /> Result := 0;<br /> end;</p> <p>end.<br />

My original optimization had a bug in it, but Bryan Mayland fixed it for me. This is old code, and there are probably some options to optimize it better. I’d love input, suggestions, etc.

Note that overflow is possible for intermediate data (Factorial), while result still fits in Int64. If this situation should be taken into account, it would better to use next approach:

function CombinationCount(n, k: Cardinal): Int64;

var

i: Cardinal;

begin

Result := 1;

if k > n – k then

k := n – k;

for i := 1 to k do

Result := (Result * (n – i + 1)) div i;

end;

Also Permutation can be reduced to just

result := Factorial(ACount, AChoose + 1);