# Factorials, Combinations & Permutaions

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.

```unit FactCombPerm;

interface

// Parameters are Cardinal because Int64 isn't Ordinal
//  Besides, Factorial(100) will overflow Int64 already.
function Factorial(const ANumber: Cardinal): Int64; overload;
function Factorial(const ANumber: Cardinal;
function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;
function Combination(const ACount, AChoose: Cardinal): Int64;
function Permutation(const ACount, AChoose: Cardinal): Int64;

implementation

function Factorial(const ANumber: Cardinal): Int64; overload;
// n! = n * (n-1) . . . n(2)
var
lCtr: Cardinal;
begin
Result := 1;
for lCtr := ANumber downto 2 do
Result := Result * lCtr;
end;

function Factorial(const ANumber: Cardinal;
// Factorial with a stop point (needed in the optimized Combination routine
// if no AStop is specified then is the same as Factorial
var
lCtr: Cardinal;
begin
Result := 1;
if ANumber >= AStop then
for lCtr := ANumber downto AStop do
Result := Result * lCtr;
end;

function CombinationUnOpt(const ACount, AChoose: Cardinal): Int64;
// n!
// n_C_k = ----------
// k!(n - k)!
begin
if AChoose < ACount then
Result := Factorial(ACount)
div (Factorial(AChoose) * Factorial(ACount - AChoose))
else
Result := 0;
end;

function Combination(const ACount, AChoose: Cardinal): Int64;
// n!
// n_C_k = ----------
// k!(n - k)!
// with optimizations even!
begin
if AChoose < ACount then
Result := Factorial(ACount, succ(ACount - AChoose))
div (Factorial(AChoose))
else
Result := 0;
end;

function Permutation(const ACount, AChoose: Cardinal): Int64;
// n!
// n_P_k = --------
// (n - k)!
begin
if AChoose < ACount then
Result := Factorial(ACount)
div Factorial(ACount - AChoose)
else
Result := 0;
end;

end.
```

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.

This entry was posted in Source Code. Bookmark the permalink.

### 2 Responses to Factorials, Combinations & Permutaions

1. MBo says:

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;

2. Uwe Raabe says:

Also Permutation can be reduced to just

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.