using System;
using System.Collections.Generic;

namespace DominionBase.Utilities
{
	public static class PermutationsAndCombinations
	{
		// Provide a cache of values so we're not doing this a lot for large numbers.
		// Perhaps this is silly -- it's a memory vs. computation speed tradeoff.
		private static readonly Dictionary<int, long> CacheFactorial = new Dictionary<int, long>();
		private static readonly Dictionary<Tuple<int, int>, long> CacheFactorialDivision = new Dictionary<Tuple<int, int>, long>();

		public static long nCr(int n, int r)
		{
			// naive: return Factorial(n) / Factorial(r) * Factorial(n - r);
			return nPr(n, r) / Factorial(r);
		}

		public static long nPr(int n, int r)
		{
			// naive: return Factorial(n) / Factorial(n - r);
			return FactorialDivision(n, n - r);
		}

		private static long FactorialDivision(int topFactorial, int divisorFactorial)
		{
			var key = Tuple.Create(topFactorial, divisorFactorial);
			if (CacheFactorialDivision.ContainsKey(key))
				return CacheFactorialDivision[key];

			long result = 1;
			for (var i = topFactorial; i > divisorFactorial; i--)
				result *= i;
			return CacheFactorialDivision[key] = result;
		}

		private static long Factorial(int i)
		{
			if (CacheFactorial.ContainsKey(i))
				return CacheFactorial[i];

			if (i <= 1)
				return 1;
			return CacheFactorial[i] = i * Factorial(i - 1);
		}
	}
}