Generate constexpr array (error: the value of 'sum' is not usable in a constant expression)

Question

问题

我需要将整数 m 的所有可能分区生成为 j 个元素 a_k 的总和，其中每个 a_k 可以是 -1 、0 或 1。这是一个确定性算法，因此它应该能够在编译时实现它。我想 return 一个 std::array 所有可能的组合如 constexpr.

我的算法

简单明了，总共有3^j种组合。所以我们遍历所有这些并检查总和是否为 m。有效组合的总数将为

\sum_{k=m}^{\lfloor (m+j)/2\rfloor}\binom{j}{k}\binom{j-k}{k-m}

因此我们可以计算出数组的大小（j乘以上面的数字），然后简单地把我们通过暴力获得的所有数字组合排队。

我的代码

Check it on Godbolt

我得到错误

error: the value of 'sum' is not usable in a constant expression 88 | if constexpr( sum == m )

但是我没看到，sum 在编译时是如何不知道的。

我该如何解决这个问题？

#include <array>
#include <iostream>
#include <utility>

/** constexpr for loop **/
template <auto Start, auto End, auto Inc, class F>
constexpr void constexpr_for(F&& f)
{
    if constexpr (Start < End)
    {
        f(std::integral_constant<decltype(Start), Start>());
        constexpr_for<Start + Inc, End, Inc>(f);
    }
}

/** constexpr binomials **/

template<std::size_t n, std::size_t k>
struct Binomial
{
  constexpr static std::size_t value =  (Binomial<n-1,k-1>::value + Binomial<n-1,k>::value);
};

template<>
struct Binomial<0,0>
{
  constexpr static std::size_t value = 1;
};

template<std::size_t n>
struct Binomial<n,0>
{
  constexpr static std::size_t value = 1;
};

template<std::size_t n>
struct Binomial<n,n>
{
  constexpr static std::size_t value = 1;
};

template<std::size_t n, std::size_t k>
constexpr std::size_t binomial()
{
  return Binomial<n,k>::value;
}

/** formula from the picture **/

template<std::size_t j, std::size_t m>
constexpr std::size_t n()
{

    std::size_t result = 0;
    constexpr_for<m, (j+m)/2+1, 1>([&result](auto k){
        result += binomial<j, k>() * binomial<j-k, k-m>();
        });
    return result;
}

/** constexpr power function **/

template<std::size_t i, std::size_t j>
struct pow_t
{
    constexpr static std::size_t value = i * pow_t<i, j-1>::value;
};

template<std::size_t i>
struct pow_t<i, 0>
{
    constexpr static std::size_t value = 1;
};

template<std::size_t i, std::size_t j>
constexpr std::size_t pow()
{
    return pow_t<i, j>::value;
}

/** actual function in question **/


template<std::size_t j, std::size_t m>
constexpr std::array<int, j*n<j,m>()> integer_compositions()
{
    std::array<int, j*n<j,m>()> result;
    std::size_t i = 0;
    constexpr_for<0, pow<3, j>(), 1>([&](auto k)
    {
        std::array<std::size_t, j> partition;
        std::size_t sum = 0;
        constexpr_for<0, j, 1>([&](auto l)
        {
            partition[l] = -((k/static_cast<std::size_t>(pow<3,l>()))%3-1);
            sum += partition[l];
        });
        if constexpr( sum == m ) // line 88
        {
            constexpr_for<0, j, 1>([&](auto l)
            {
                result[j*i + l] = partition[l];
            });
            ++i;
        }
    });
    return result;
}

int main()
{
    constexpr auto list = integer_compositions<3, 1>();
    return EXIT_SUCCESS;
}

Answer 1

您混淆了 constexpr 函数的用途。 constexpr 函数既可以在运行时执行，也可以作为 constant expression 的一部分执行，这取决于您如何使用该函数（并且可能编译器是否希望在编译时进行优化）。

您不需要所有这些模板化函数，因为 constexpr 函数的全部目的是为了清楚起见而避免使用它们，例如，您的 binomial 函数可以简单地是：

constexpr std::size_t binomial(std::size_t n, std::size_t k) {
    if (k == 0 || n == k) {
        return 1;
    }
    else {
        return binomial(n - 1, k - 1) + binomial(n - 1, k);
    }
}

然后你可以这样做：

// binomial(3, 2) is evaluated at compile-time
std::array<int, binomial(3, 2)> x;
static_assert(x.size() == 3);

除了最后一个 (integer_compositions) 之外的所有函数都可以这样做，因为 return 类型取决于参数，因此您需要一个模板。

您的代码中还有其他问题，例如，您需要在 constexpr 函数中初始化 std::array，因此 std::array<..., ...> result{}（注意此处的 {}） .

下面是您的代码的工作版本，它没有使用所有这些模板（这需要 C++20，但这只是因为 operator== 对于 std::array 只是 constexpr自 C++20 起):

#include <array>
#include <iostream>

/** constexpr binomials **/

constexpr std::size_t binomial(std::size_t n, std::size_t k) {
    if (k == 0 || n == k) {
        return 1;
    }
    else {
        return binomial(n - 1, k - 1) + binomial(n - 1, k);
    }
}

/** formula from the picture **/

constexpr std::size_t n(std::size_t j, std::size_t m)
{

    std::size_t result = 0;
    for (std::size_t k = m; k <= (j + m) / 2; ++k) {
        result += binomial(j, k) * binomial(j - k, k - m);
    }
    return result;
}

/** constexpr power function **/

constexpr std::size_t pow(std::size_t a, std::size_t n) {
    std::size_t r = 1;
    while (n--) {
        r *= a;
    }
    return r;
}

/** actual function in question **/


template<std::size_t j, std::size_t m>
constexpr std::array<int, j*n(j, m)> integer_compositions()
{
    std::array<int, j*n(j, m)> result{};
    std::size_t i = 0;
    for (std::size_t k = 0; k < ::pow(3, j); ++k) {
        std::array<std::size_t, j> partition{};
        std::size_t sum = 0;
        for (std::size_t l = 0; l < j; ++l) {
            partition[l] = -((k/static_cast<std::size_t>(::pow(3, l)))%3-1);
            sum += partition[l];
        }
        if (sum == m) // line 88 
        {
            for (std::size_t l = 0; l < j; ++l) {
                result[j*i + l] = partition[l];
            }
            ++i;
        }
    }
    return result;
}

int main()
{
    static_assert(integer_compositions<3, 1>() == std::array<int, 18>{});
}

注意：静态断言显然失败了，因为我不知道这18个值是什么。

Generate constexpr array (error: the value of 'sum' is not usable in a constant expression)