///CalcNumOfCombinations returns the number of combinations a Newick can have.
///
///The number of possible combinations equals
/// !(v0 + v1 + v2 + etc)
/// N = -------------------------- / 2^number_of_symmetries
/// !v0 * !v1 * !v2 * etc
///
/// n
/// = --- / 2^number_of_symmetries
/// d
///
/// where v denotes an element in vector v in range [1,-> >
/// where v0 denotes the first element in vector v
/// and where !v0 denotes the factorial of v0
/// {factorial(!SUM(v)) product terms}
/// N = --------------------------------------------------
/// {product terms} + { number_symmetries times a '2'}
///
/// numerator_terms
/// N = --------------------------------------------------
/// denominator_terms with appended number_symmetries times a '2'
///
///From http://www.richelbilderbeek.nl/CppCalcNumOfCombinations.htm
const cln::cl_I CalcNumOfCombinations(const std::vector<int>& v)
{
assert(IsNewick(v));
//Get all positives
std::vector<cln::cl_I> positives;
Copy_if(
v.begin(),v.end(),
std::back_inserter(positives),
std::bind2nd(std::greater<cln::cl_I>(),0));
//Obtain numerator = (SUM(x))!
const int sum_values = Accumulate_if(v.begin(),v.end(),0,std::bind2nd(std::greater<int>(),0));
cln::cl_I numerator = cln::factorial(sum_values);
//Obtain factorialated positives
cln::cl_I denominator = 1;
BOOST_FOREACH(const int& i, v)
{
if (i<=0) continue;
const cln::cl_I i_temp = cln::factorial(i);
denominator*=i_temp;
}
//Obtain number_of_symmetries
const int number_of_symmetries = CalcNumOfSymmetries(v);
//Add number_of_symmetries times a 2 to denominator terms
for(int i=0; i!=number_of_symmetries; ++i)
{
const cln::cl_I i_temp = 2;
denominator*=i_temp;
}
//Return the division
numerator/=denominator;
return numerator;
}
|
