常量表达式行列式（二维 std::array）

Question

常量表达式行列式（二维 std::array）

3

我需要编写一个在编译时计算行列式的constexpr函数。最显而易见的解决方案是使用拉普拉斯展开。支持C++14。

#include <array>
#include <utility>

constexpr int get_cofactor_coef(int i, int j) {
    return (i + j) % 2 == 0 ? 1 : -1;
}

template <int N>
constexpr int determinant(const std::array<std::array<int, N>, N>& a) {
    int det = 0;

    for (size_t i = 0u; i < N; ++i) {
        det += get_cofactor_coef(i, 1) * a[i][0] * determinant<N-1>(GET_SUBMATRIX_OF_A<N-1, I, J>(a);
    }

    return det;
}

template <>
constexpr int determinant<2>(const std::array<std::array<int, 2>, 2>& a) {
    return a[0][0] * a[1][1] - a[0][1] * a[1][0];
}

template <>
constexpr int determinant<1>(const std::array<std::array<int, 1>, 1>& a) {
    return a[0][0];
}

问题在于我完全不知道如何编写GET_SUBMATRIX_OF_A。

我知道我需要：

1.生成一个序列（可能会使用std::integer_sequence）； 2.从该序列中排除第i行； 3.复制除第一（0-th）列以外的所有列；

我的constexpr技能几乎不存在。尝试将a传递给另一个函数会导致奇怪的错误，如error: '* & a' is not a constant expression。

非常感谢您的所有帮助！

- magom001

使用C++17是一个选项吗？其中许多函数都是constexpr的，例如array的at()函数，这意味着您几乎可以编写“标准”代码，并使其成为constexpr。 - AVH

很遗憾，我被明确告知要使用C++14标准... - magom001

2个回答

0

这里是一个示例实现。可能有更短或更优雅的方法，但这是一个起点。实际上，我刚意识到你的矩阵是方阵，所以在下面的代码中肯定可以省略一些模板参数。

正如我在评论中提到的，对于C++17及以上版本，很可能根本不需要这些。

首先，让我们定义一些样板文件，让我们创建并索引序列，并留下一个值（即您要跳过的行）：

#include <utility>

// Based on https://dev59.com/IWQm5IYBdhLWcg3wrAmY#32223343.
template <size_t Offset, class T1, class T2>
struct offset_sequence_merger;

template <size_t Offset, size_t... I1, size_t... I2>
struct offset_sequence_merger<Offset, std::index_sequence<I1...>, std::index_sequence<I2...>>
  : std::index_sequence<I1..., (Offset + I2)...>
{ };

template <std::size_t Excluded, std::size_t End>
using make_excluded_index_sequence = offset_sequence_merger<Excluded + 1,
  std::make_index_sequence<Excluded>,
  std::make_index_sequence<End - Excluded - 1>>;

现在让我们将其用于提取子矩阵：

#include <array>
template <class T, std::size_t N, std::size_t... Indices>
constexpr std::array<T, sizeof...(Indices)> extract_columns (
    std::array<T, N> const & source, std::index_sequence<Indices...>) {
  return { source.at(Indices)... };
}

template <class T, std::size_t N>
constexpr std::array<T, N - 1> drop_first_column (
    std::array<T, N> const & source) {
  return extract_columns(source, make_excluded_index_sequence<0, N>());
}

template <class T, std::size_t Rows, std::size_t Cols, std::size_t... RowIndices>
constexpr auto create_sub_matrix (
    std::array<std::array<T, Cols>, Rows> const & source,
    std::index_sequence<RowIndices...>) 
    -> std::array<std::array<T, Cols - 1>, sizeof...(RowIndices)> {
  return { drop_first_column(source.at(RowIndices))... };
}

template <std::size_t ExcludedRow, class T, std::size_t Rows, std::size_t Cols>
constexpr auto create_sub_matrix (
    std::array<std::array<T, Cols>, Rows> const & source)
    -> std::array<std::array<T, Cols - 1>, Rows - 1> {
  return create_sub_matrix(source,
    make_excluded_index_sequence<ExcludedRow, Rows>());
}

最后，这里有一些代码展示了上述内容似乎做到了它应该做的事情。你可以在Wandbox中看到它的实际效果：

#include <iostream>
#include <string>

template <class T>
void print_seq (std::integer_sequence<T> const & /* seq */) {
  std::cout << '\n';
}

template <class T, T Head, T... Tail>
void print_seq (std::integer_sequence<T, Head, Tail...> const & /* seq */) {
  std::cout << Head << ' ';
  print_seq(std::integer_sequence<T, Tail...>{});
}

template <class T, std::size_t N>
void print_array (std::array<T, N> const & src) {
  std::string sep = "";
  for (auto const & e : src) {
    std::cout << sep << e;
    sep = " ";
  }
  std::cout << '\n';
}

template <class T, std::size_t N, std::size_t M>
void print_matrix (std::array<std::array<T, N>, M> const & src) {
  for (auto const & row : src) { print_array(row); }
}

int main () {
  auto indexSeqA = make_excluded_index_sequence<0, 3>(); print_seq(indexSeqA);
  auto indexSeqB = make_excluded_index_sequence<1, 3>(); print_seq(indexSeqB);
  auto indexSeqC = make_excluded_index_sequence<2, 3>(); print_seq(indexSeqC);
  std::cout << '\n';

  std::array<int, 3> arr = { 1, 7, 9 };
  print_array(arr); std::cout << '\n';

  std::array<std::array<int, 3>, 3> matrix = {{
      { 0, 1, 2 }
    , { 3, 4, 5 }
    , { 6, 7, 8 }
  }};
  print_matrix(matrix); std::cout << '\n';

  print_matrix(create_sub_matrix<0>(matrix)); std::cout << '\n';
  print_matrix(create_sub_matrix<1>(matrix)); std::cout << '\n';
}

希望这足以帮助您完全实现 determinant 函数。(附注：在调用它时不需要显式提供 size_t 模板参数，它将从其 std::array 参数的大小自动推断。)

- AVH

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ecatmur · Accepted Answer

问题在于非const的std::array<T, N>::operator[]（返回）在C++17之前不是constexpr，这使得设置元素变得困难。

然而，有一个逃生口，就是std::get<I>(std::array&)是constexpr的，并且可以对结果执行指针算术运算，因此我们可以重写为：

a[i]  // constexpr since C++17

as

(&std::get<0>(a))[i]  // constexpr in C++14!!

换句话说，我们使用 std::get 获取数组的第一个成员的constexpr引用，将其指针化，并在指针和索引上使用内置的[]运算符。

然后，一个两级的数组成员访问a[i][j]变得非常丑陋但仍然是constexpr：(&std :: get<0>((&std :: get<0>(a))[i])) [j]，这意味着我们可以写一个普通的constexpr函数“get_submatrix_of_a”：

template<std::size_t N>
constexpr std::array<std::array<int, N - 1>, N - 1>
get_submatrix_of_a(const std::array<std::array<int, N>, N>& a, int i, int j) {
    std::array<std::array<int, N - 1>, N - 1> r{};
    for (int ii = 0; ii != N - 1; ++ii)
        for (int jj = 0; jj != N - 1; ++jj)
            (&std::get<0>(((&std::get<0>(r))[ii])))[jj] = a[ii + (ii >= i ? 1 : 0)][jj + (jj >= j ? 1 : 0)];
    return r;
}

请记住，在C++14中const std::array<T，N> :: operator [] 已经是constexpr，因此我们无需重新编写较小构造函数的右手边。