I know that constexpr is supposed to allow the elimination / simplification of many template programming tricks used in the past, but I'm still fairly new to C++11 on and I am having trouble understanding why, in calculating the combination function:
C(n,r) = n!/(r!(n-r)!) = C(n-1,r-1) + C(n-1,r)
The recursive approach, which is ridiculously slow when executed at runtime as would be expected, but allows calculations of C(n,r) for much larger values, works just fine with templates, but I cannot get it to work with constexpr. Here is the template code I'm using:
using factorial_t = unsigned long long;
template<size_t N, size_t R>
struct recursive_combinations {
enum: factorial_t { value = recursive_combinations<N-1, R>::value +
recursive_combinations<N-1, R-1>::value};
};
template<size_t N>
struct recursive_combinations<N,0> {
enum: factorial_t { value = 1 };
};
template<size_t N>
struct recursive_combinations<N,N> {
enum: factorial_t { value = 1 };
};
and here is the constexpr version (maybe I am doing something wrong here):
constexpr const factorial_t recursiveCombinations(const size_t N, const size_t R) {
if (R == N || R == 0) return 1;
return recursiveCombinations(N-1, R) + recursiveCombinations(N-1, R-1);
}
When I try this:
constexpr auto comb1_50_30 = recursive_combinations<50,30>::value;
everything is just fine, and I get the expected result of 47,129,212,243,960, which is unobtainable from calculating the factorials.
However, when I try this:
constexpr auto comb2_50_30 = recursiveCombinations(50, 30);
the compiler (clang v5.0.1, set to C++17 mode) complains that comb2_50_30 must be initialized by a constant expression.
Can somebody help me figure out what I'm doing wrong or if there is a way to get this to work with constexpr (and if not, why not)?
At the cost of reducing the limit of the result by one factor of min(r, n-r), you can use the following far more efficient implementation:
constexpr uint64_t efficientCombinations(uint64_t n, uint64_t r)
{
uint64_t accum = 1U;
if (n - r > r) r = n - r;
for( uint64_t x = 1; x <= n - r; ++x )
{
accum *= (r + x);
accum /= x;
}
return accum;
}
For compatibility with C++11, transforming this iteration to recursion is straightforward if a bit messy.
(Note: depending on what the question meant by "get this to work", changing the algorithm like this might not be the desired approach... but it's too big for a comment)
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加