基于装饰器模式实现n阶逆矩阵的求解

首先mn矩阵只是一个mn的数表，首先对于一个数表，需要有四个基本行为即设置某行某列的值，获取某行某列的值，获取行数列数，还可基于该这些行为为其实现一些便捷通用的函数。如打印输出该矩阵。故所有的矩阵可抽象成一个抽象的接口。

矩阵接口定义

接口定义如下：

/// 矩阵接口
template <class T>
class IMatrix {
   public:
    // 获得行
    virtual int cols() = 0;
    // 获得列
    virtual int rows() = 0;
    // 设置元素
    virtual void set(int row, int col, T e) = 0;
    // 获取元素
    virtual T get(int row, int col) = 0;

    virtual string to_string() {
        stringstream ss;
        for (int i = 0; i < rows(); i++) {
            ss << "[";
            for (int j = 0; j < cols(); j++) {
                ss << get(i, j);
                if (j != cols() - 1) ss << ",";
            }
            ss << "]" << endl;
        }
        return ss.str();
    }
};

普通的数值矩阵的存储

该接口定义便为矩阵这种数据结构的逻辑存储结构。

下面使用常规的数值矩阵的物理存储结构为该接口的实现类之一，我们可以通过一维数组基于行优先的规则定义出二维的矩阵物理存储结构。

类的定义如下：

/// 一般的数值矩阵
template <class T>
class NormalMatrix : public IMatrix<T> {
   private:
    vector<T> _vec;
    int _cols, _rows;

   public:
    explicit NormalMatrix(int rows, int cols, T defaultValue) {
        _cols = cols;
        _rows = rows;
        _vec = vector<T>(rows * cols, defaultValue);
    }

    // 复制矩阵
    explicit NormalMatrix(IMatrix<T>& mat) {
        _cols = mat.cols();
        _rows = mat.rows();
        _vec = vector<T>(_rows * _cols);
        for (int i = 0; i < _rows; i++) {
            for (int j = 0; j < _cols; j++) {
                _vec[i * _cols + j] = mat.get(i, j);
            }
        }
    }

    // 获得行
    inline int cols() override { return _cols; }
    // 获得列
    inline int rows() override { return _rows; }
    // 设置元素
    inline void set(int row, int col, T e) override {
        _vec[row * cols() + col] = e;
    }
    // 获取元素
    inline T get(int row, int col) override { return _vec[row * cols() + col]; }
};

转置矩阵求解

如何求一个矩阵的转置矩阵？
实际上我们仅需要在逻辑上进行行列互换即可得到转置矩阵。

template <class T>
class TransposeMatrix : public IMatrix<T> {
   private:
    IMatrix<T>& _mat;

   public:
    explicit TransposeMatrix(IMatrix<T>& mat) : _mat(mat) {}
    // 获得行
    inline int cols() override { return _mat.rows(); }
    // 获得列
    inline int rows() override { return _mat.cols(); }
    // 设置元素
    inline void set(int row, int col, T e) override { _mat.set(col, row, e); }
    // 获取元素
    inline T get(int row, int col) override { return _mat.get(col, row); }
};

上述代码便实现了逻辑上的转置，由于IMatrix接口实现了默认函数to_string，且to_string是基于四个纯虚函数实现的，故to_string函数对于所有的子类依然有效。通过构造函数传入该接口的实现类的对象为其重新装饰一些新的行为而外部对其使用的方式不变，即接口不变，即装饰器模式。

余子矩阵求解

在行列式的求解中，我们会求余子式，而某个元素对应的余子矩阵对应的行列式便为余子式。

如果我们要求矩阵$A_{ij}$的余子矩阵B，则矩阵B对应的行列将-1，矩阵B对应的元素编号可以通过逻辑计算映射到矩阵A中的矩阵编号，代码实现如下：

template <class T>
class CominorMatrix : public IMatrix<T> {
   private:
    IMatrix<T>& _mat;
    int _row;
    int _col;

   public:
    explicit CominorMatrix(IMatrix<T>& mat, int row, int col)
        : _mat(mat), _row(row), _col(col) {}

    // 获得行
    inline int cols() override { return _mat.cols() - 1; }
    // 获得列
    inline int rows() override { return _mat.rows() - 1; }
    // 设置元素
    inline void set(int row, int col, T e) override {
        __throw_runtime_error("CominorMatrix cannot be set value");
    }
    // 获取元素
    inline T get(int row, int col) override {
        return _mat.get(row < _row ? row : row + 1, col < _col ? col : col + 1);
    }
};

实现行列式求解

实现了余子矩阵的求法之后，我们便可基于行列式展开的递归定义，尝试写出行列式计算的函数

template <class T>
T determinant(IMatrix<T>& mat) {
    if (mat.cols() != mat.rows()) {
        string s = mat.to_string();
        s += "determinant matrix columns not equal to rows";
        __throw_runtime_error(s.c_str());
    }
    
    // 只有一个数字的1*1矩阵，直接返回它本身
    if (mat.cols() == 1) {
        return mat.get(0, 0);
    }

    T sig = 1;
    T sum = 0;
    // 按第0行的每一列元素展开
    for (int c = 0; c < mat.cols(); c++) {
        // 求余子式
        CominorMatrix<T> cm(mat, 0, c);
        T cominor = determinant(cm);

        // 代数余子式累加
        sum += sig * mat.get(0, c) * cominor;
        sig *= -1; 
    }
    return sum;
}

伴随矩阵求解

基于行列式计算的函数，我们又可以进一步编写出伴随矩阵的求解，依然使用装饰器模式如下：

template <class T>
class AdjugateMatrix : public IMatrix<T> {
   private:
    IMatrix<T>& _mat;

   public:
    explicit AdjugateMatrix(IMatrix<T>& mat) : _mat(mat) {}
    // 获得行
    inline int cols() override { return _mat.rows(); }
    // 获得列
    inline int rows() override { return _mat.cols(); }
    // 设置元素
    inline void set(int row, int col, T e) override {
        __throw_runtime_error("AdjugateMatrix cannot be set value");
    }
    // 获取元素
    inline T get(int row, int col) override {
        // 当row+col为偶数时为正
        int sgn = (row + col) % 2 == 0 ? 1 : -1;
        CominorMatrix<T> cm(_mat, col, row);
        // 求余子式
        T cominor = determinant(cm);
        // 代数余子式
        return sgn * cominor;
    }
};

矩阵变换装饰器

为了便于对矩阵上的每个数值进行统一的逻辑上的映射到另一个值，即每个元素可经过某个函数f完成变换，可编写装饰器如下：

template <class T,class E>
class TransformMatrix : public IMatrix<E> {
   private:
    IMatrix<T>& _mat;
    function<E(int, int, T)> _proc;

   public:
    explicit TransformMatrix(IMatrix<T>& mat, function<E(int, int, T)> proc)
        : _mat(mat), _proc(proc) {}
    // 获得行
    inline int cols() override { return _mat.cols(); }
    // 获得列
    inline int rows() override { return _mat.rows(); }
    // 设置元素
    inline void set(int row, int col, E e) override {
        __throw_runtime_error("InversionMatrix cannot be set value");
    }
    // 获取元素
    inline E get(int row, int col) override {
        return _proc(row, col, _mat.get(row, col));
    }
};

至此，我们便可以完成逆矩阵求解的装饰器，

逆矩阵求解

通过逆矩阵的概念，$A^{-1}=|A|^{-1} A^*$可知逆矩阵的定义代码如下：

template <class T>
class InversionMatrix : public IMatrix<double> {
   private:
    IMatrix<T>& _mat;

   public:
    explicit InversionMatrix(IMatrix<T>& mat) : _mat(mat) {}
    // 获得行
    inline int cols() override { return _mat.cols(); }
    // 获得列
    inline int rows() override { return _mat.rows(); }
    // 设置元素
    inline void set(int row, int col, double e) override {
        __throw_runtime_error("InversionMatrix cannot be set value");
    }
    // 获取元素
    inline double get(int row, int col) override {
        T det = determinant(_mat);
        AdjugateMatrix<T> am(_mat);
        TransformMatrix<T,double> tfm(am,
                               [det](int row, int col, T e) { return double(e) / double(det); });
        return tfm.get(row, col);
    }
};

测试代码

int main() {
    const int m = 3;
    NormalMatrix<int> nm(m, m, 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            nm.set(i, j, i * m + j);
        }
    }

    InversionMatrix<int> im(nm);
    cout<< im.to_string()<<endl;
    return 0;
}