#include "combinatorics.h"

integer factorial(integer n)
{
	if ( n < 0 )
		return 0;

	integer result = 1;
	for ( integer i = 1; i <= n; ++i )
		result *= i;
	return result;
}

integer permutations_no_repetition(integer n, integer r)
{
	if ( r < 0 || n < 0 || r > n )
		return 0;

	// P(n,r) = n! / (n - r)!
	// overflow:
	// return factorial(n) / factorial(n - r);

	integer result = 1;
	for ( integer i = n; i > (n - r); --i )
		result *= i;
	return result;
}

integer permutations_with_repetition(integer n, integer r)
{
	if ( r < 0 || n < 0 || r > n )
		return 0;

	// n^r
	integer result = 1;
	for( integer i = 1; i <= r; ++i )
		result *= n;
	return result;
}

integer combinations_no_repetition(integer n, integer r)
{
	if ( r < 0 || n < 0 || r > n )
		return 0;

	// P(n,r) = n! / (n - r)!
	// overflow:
	// return factorial(n) / factorial(n - r);

	integer result = 1;
	integer max_denominator = max(r, n - r);
	for ( integer i = n; i > max_denominator; --i )
		result *= i;
	return result / factorial(min(r, n - r));
}

integer combinations_with_repetition(integer n, integer r)
{
	if ( r < 0 || n < 0 || r > n )
		return 0;

	// P(n,r) = n! / (n - r)!
	// overflow:
	// return factorial(n) / factorial(n - r);

	integer result = 1;
	integer max_denominator = max(r, n - 1);
	for ( integer i = n + r - 1; i > max_denominator; --i )
		result *= i;
	return result / factorial(min(r, n - 1));
}