Linalg IHW 2 task 4

main.cpp

#include <iostream>
#include <algorithm>
#include "matrix.h"
#include "polynomial.h"
#include "permutation.h"

using namespace std;

using P_T = Polynomial<int>;
#define x P_T(make_pair(1, 1))

int main() {

    Matrix<P_T> mat(vector<vector<P_T>>{
        vector<P_T>{3, 5, x, 9, 4, 2, 3},
        vector<P_T>{5, x, 0, 5, 9, 7, 7},
        vector<P_T>{x, 0, 0, 6, 3, 8, x},
        vector<P_T>{9, 5, 6, 0, 3, x, 1},
        vector<P_T>{4, 9, 3, 3, x, 0, 5},
        vector<P_T>{2, 7, 8, x, 0, 4, 4},
        vector<P_T>{3, 7, x, 1, 5, 4, 8}
    });
    cout << "Determinant: " << mat.get_determinant() << endl;
    cout << "Coefficient next to x^5: " << mat.get_determinant()[5] << endl;
}

matrix.h

#include <iostream>
#include <vector>
#include "permutation.h"

template<typename T>
class Matrix {
private:
    std::vector<std::vector<T>> mat;

public:
    Matrix() {}

    explicit Matrix(const std::vector<std::vector<T>>& in_mat) : mat(in_mat) {}

    std::pair<size_t, size_t>  size() const {
        if (mat.empty())
            return std::make_pair(0, 0);
        return std::make_pair(mat.size(), mat[0].size());
    }

    Matrix& operator+=(const Matrix<T>& other) {
        for (size_t i = 0; i < mat.size(); ++i) {
            for (size_t j = 0; j < mat[i].size(); ++j) {
                mat[i][j] += other.mat[i][j];
            }
        }
        return *this;
    }

    template<typename T1>
    Matrix& operator*=(const T1& scal) {
        for (size_t i = 0; i < mat.size(); ++i) {
            for (size_t j = 0; j < mat[i].size(); ++j) {
                mat[i][j] *= scal;
            }
        }
        return *this;
    }

    template<typename T1>
    Matrix operator*(const T1& num) const {
        Matrix<T> res(mat);
        res *= num;
        return res;
    }

    Matrix operator+(const Matrix<T>& other) const {
        Matrix<T> res(mat);
        res += other;
        return res;
    }

    Matrix& operator*=(const Matrix& other) {
        std::vector<std::vector<T>> tmp(this->size().first, std::vector<T>(other.size().second));
        for (size_t i = 0; i < this->size().first; ++i) {
            for (size_t j = 0; j < other.size().second; ++j) {
                for (size_t t = 0; t < other.size().first; ++t) {
                    tmp[i][j] += mat[i][t] * other.mat[t][j];
                }
            }
        }
        mat = std::move(tmp);
        return *this;
    }

    Matrix operator*(const Matrix<T>& num) const {
        Matrix<T> res(mat);
        res *= num;
        return res;
    }

    Matrix& transpose() {
        std::vector<std::vector<T>> newmat(this->size().second, std::vector<T>(this->size().first));
        for (size_t i = 0; i < this->size().first; ++i) {
            for (size_t j = 0; j < this->size().second; ++j) {
                newmat[j][i] = mat[i][j];
            }
        }
        this->mat = std::move(newmat);
        return *this;
    }

    Matrix transposed() const {
        std::vector<std::vector<T>> newmat(this->size().second, std::vector<T>(this->size().first));
        for (size_t i = 0; i < this->size().first; ++i) {
            for (size_t j = 0; j < this->size().second; ++j) {
                newmat[j][i] = mat[i][j];
            }
        }
        return Matrix(std::move(newmat));
    }

    friend std::ostream& operator<<(std::ostream& os, const Matrix<T>& matrix) {
        for (size_t i = 0; i < matrix.size().first; ++i) {
            for (size_t j = 0; j < matrix.size().second; ++j) {
                os << matrix.mat[i][j];
                if (j + 1 < matrix.size().second)
                    os << '\t';
            }
            if (i + 1 < matrix.size().first)
                os << '\n';
        }
        return os;
    }

    T get_determinant() const {
        T res = 0;
        Permutation cur_perm(size().first);
        do {
            T cur = cur_perm.get_sign();
            for (size_t i = 0; i < size().first; ++i) {
                cur *= mat[i][cur_perm[i]];
            }
            res += cur;
        } while (cur_perm.next());
        return res;
    }
};

permutation.h

#pragma once

#include <iostream>
#include <vector>

class Permutation {
public:
    std::vector<size_t> perm;

public:

    Permutation() {}

    Permutation(size_t n) {
        perm.reserve(n);
        for (size_t i = 0; i < n; ++i)
            perm.push_back(i);
    }

    Permutation(std::vector<size_t> _perm): perm(_perm) {
        if (std::find(perm.begin(), perm.end(), 0) == perm.end())
            for (size_t i = 0; i < perm.size(); ++i)
                --perm[i];
    }

    bool next() {
        if (perm.size() < 2)
            return false;
        size_t cur = perm.size() - 1;
        while (perm[cur - 1] > perm[cur]) {
            --cur;
            if (cur == 0)
                return false;
        }

        size_t nxt = perm.size() - 1;
        while (nxt > cur && perm[nxt] < perm[cur - 1])
            --nxt;

        std::swap(perm[nxt], perm[cur - 1]);

        std::reverse(perm.begin() + cur, perm.end());
        return true;
    }

    size_t size() const {
        return perm.size();
    }

    size_t operator[](size_t p) const {
        return perm[p];
    }

    size_t& operator[](size_t p) {
        return perm[p];
    }

    friend std::ostream& operator<<(std::ostream &os, const Permutation& P) {
        for (size_t i = 0; i < P.size(); ++i)
            os << i + 1 << '\t';
        os << std::endl;
        for (size_t i = 0; i < P.size(); ++i)
            os << P.perm[i] + 1 << '\t';
        return os;
    }

    Permutation& operator*=(const Permutation& other) {
        std::vector<size_t> tmp(size());
        for (size_t i = 0; i < size(); ++i) {
            tmp[i] = other[perm[i]];
        }
        perm = std::move(tmp);
        return *this;
    }

    friend Permutation operator*(const Permutation& P1, const Permutation& P2) {
        Permutation tmp(P1);
        tmp *= P2;
        return tmp;
    }

    Permutation inversed() const {
        Permutation tmp(size());
        for (size_t i = 0; i < size(); ++i)
            tmp[perm[i]] = i;
        return tmp;
    }

    bool operator==(const Permutation& P) const {
        return perm == P.perm;
    }

    size_t get_inversions() const {
        size_t res = 0;
        for (size_t i = 0; i < size(); ++i) {
            for (size_t j = i + 1; j < size(); ++j) {
                if (perm[j] < perm[i])
                    ++res;
            }
        }
        return res;
    }

    int get_sign() const {
        size_t res = get_inversions();
        if (res % 2 == 0)
            return 1;
        else
            return -1;
    }

};

polynomial.h

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

template <typename T>
T bin_power(const T& a, int p) {
    if (p == 0)
        return T(1);
    if (p == 1)
        return a;
    T x = bin_power(a, p / 2);
    x = x * x;
    if (p % 2 == 1)
        x = x * a;
    return x;
}

template<typename T = int>
class Polynomial {
public:
    std::vector<std::pair<int, T>> coeffs;

    Polynomial() {
        coeffs.emplace_back(0, T());
    }

    explicit Polynomial(const std::vector<T>& in_coeffs) {
        int cnt = 0;
        for (const T& el : in_coeffs) {
            if (el != T(0))
                coeffs.emplace_back(cnt, el);
            cnt++;
        }
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
    }

    explicit Polynomial(const std::pair<int, T>& monom) {
        coeffs.push_back(monom);
    }

    Polynomial(const T& single) {
        coeffs.emplace_back(0, single);
    }

    template<typename It>
    Polynomial(It first, It last) {
        int cnt = 0;
        while (first != last) {
            if (*first != T(0))
                coeffs.emplace_back(cnt, *first);
            cnt++;
            ++first;
        }
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
    }

    Polynomial& operator+=(const Polynomial<T>& other) {
        auto first1 = other.coeffs.begin();
        auto first2 = coeffs.begin();
        std::vector<std::pair<int, T>> new_coeffs;
        while (first1 != other.coeffs.end() && first2 != coeffs.end()) {
            if (first1->first < first2->first) {
                if (first1->second != T(0))
                    new_coeffs.push_back(*first1);
                first1++;
            } else if (first1->first == first2->first) {
                if (first1->second + first2->second != T(0))
                    new_coeffs.emplace_back(first1->first, first1->second + first2->second);
                first1++;
                first2++;
            } else {
                if (first2->second != T(0))
                    new_coeffs.push_back(*first2);
                first2++;
            }
        }
        while (first1 != other.coeffs.end()) {
            if (first1->second != T(0))
                new_coeffs.push_back(*first1);
            first1++;
        }
        while (first2 != coeffs.end()) {
            if (first2->second != T(0))
                new_coeffs.push_back(*first2);
            first2++;
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator+(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp += P2;
        return tmp;
    }

    Polynomial& operator-=(const Polynomial<T>& other) {
        auto first1 = other.coeffs.begin();
        auto first2 = coeffs.begin();
        std::vector<std::pair<int, T>> new_coeffs;
        while (first1 != other.coeffs.end() && first2 != coeffs.end()) {
            if (first1->first < first2->first) {
                if (first1->second != T(0))
                    new_coeffs.emplace_back(first1->first, -first1->second);
                first1++;
            } else if (first1->first == first2->first) {
                if (first1->second - first2->second != T(0))
                    new_coeffs.emplace_back(first1->first, first2->second - first1->second);
                first1++;
                first2++;
            } else {
                if (first2->second != T(0))
                    new_coeffs.push_back(*first2);
                first2++;
            }
        }
        while (first1 != other.coeffs.end()) {
            if (first1->second != T(0))
                new_coeffs.emplace_back(first1->first, -first1->second);
            first1++;
        }
        while (first2 != coeffs.end()) {
            if (first2->second != 0)
                new_coeffs.push_back(*first2);
            first2++;
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator-(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp -= P2;
        return tmp;
    }

    Polynomial& operator*=(const Polynomial<T>& other) {
        std::map<int, T> tmp;
        for (const auto& first : coeffs) {
            for (const auto& second : other.coeffs) {
                if (first.second != T(0) && second.second != T(0))
                    tmp[first.first + second.first] += first.second * second.second;
            }
        }
        std::vector<std::pair<int, T>> new_coeffs;
        for (const auto& it : tmp) {
            if (it.second != T(0)) {
                new_coeffs.push_back(it);
            }
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator*(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp *= P2;
        return tmp;
    }

    T operator()(const T& x) const {
        T ans = T();
        for (const auto& it : coeffs) {
            ans += bin_power(x, it.first) * it.second;
        }
        return ans;
    }

    typename std::vector<std::pair<int, T>>::const_iterator begin() const {
        return coeffs.cbegin();
    }

    typename std::vector<std::pair<int, T>>::const_iterator end() const {
        return coeffs.cend();
    }

    friend std::ostream& operator<<(std::ostream &out, const Polynomial<T>& P) {
        bool was_output = false;
        for (auto it = P.coeffs.rbegin(); it != P.coeffs.rend(); ++it) {
            if (it->second == T(0))
                continue;
            if (it->second < T(0))
                out << '-';
            else if (was_output)
                out << '+';
            if (abs(it->second) != T(1) || it->first == 0)
                out << std::abs(it->second);
            if ((abs(it->second) != T(1) || it->first == 0) && it->first != 0)
                out << '*';
            if (it->first != 0)
                out << 'x';
            if (it->first > 1)
                out << '^' << it->first;
            was_output = true;
        }
        if (!was_output)
            out << T(0);
        return out;
    }

    T operator[](int p) const {
        for (const auto& it : coeffs) {
            if (it.first == p)
                return it.second;
        }
        return T(0);
    }

    int Degree() const {
        int ans = -1;
        for (const auto& it : coeffs) {
            if (it.second != T(0))
                ans = it.first;
        }
        return ans;
    }

    Polynomial& operator/=(const Polynomial &P) {
        std::vector<std::pair<int, T>> new_coeffs;
        while (!coeffs.empty() && coeffs.rbegin()->first >= P.coeffs.rbegin()->first) {
            T coef = coeffs.rbegin()->second / P.coeffs.rbegin()->second;
            int pow = coeffs.rbegin()->first - P.coeffs.rbegin()->first;
            if (coef == T(0))
                break;
            *this -= P * Polynomial(std::make_pair(pow, coef));
            if (coef != T(0))
                new_coeffs.emplace_back(pow, coef);
        }
        reverse(new_coeffs.begin(), new_coeffs.end());
        coeffs = std::move(new_coeffs);
        return *this;
    }

    friend Polynomial operator/(const Polynomial& P1, const Polynomial& P2) {
        Polynomial tmp(P1);
        tmp /= P2;
        return tmp;
    }

    Polynomial& operator%=(const Polynomial &P) {
        while (!coeffs.empty() && coeffs.rbegin()->first >= P.coeffs.rbegin()->first) {
            T coef = coeffs.rbegin()->second / P.coeffs.rbegin()->second;
            int pow = coeffs.rbegin()->first - P.coeffs.rbegin()->first;
            if (coef == T(0))
                break;
            *this -= P * Polynomial(std::make_pair(pow, coef));
        }
        while (!coeffs.empty() && coeffs.back().second == T(0))
            coeffs.pop_back();
        return *this;
    }

    friend Polynomial operator%(const Polynomial& P1, const Polynomial& P2) {
        Polynomial tmp(P1);
        tmp %= P2;
        return tmp;
    }

    friend Polynomial operator&(const Polynomial &P1, const Polynomial &P2) {
        Polynomial result;
        for (const auto& first : P1) {
            result += bin_power(P2, first.first) * first.second;
        }
        return result;
    }

    friend Polynomial operator,(const Polynomial& P1, const Polynomial& P2) {
        if (P1.Degree() == -1)
            return P2;
        auto tmp = (P2 % P1, P1);
        if (tmp.coeffs.back().second != T(0))
            tmp /= tmp.coeffs.back().second;
        return tmp;
    }
};

template<typename T1, typename T2>
bool operator==(const Polynomial<T1>& P1, const Polynomial<T2>& P2) {
    return P1.coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator==(const T1& single, const Polynomial<T2>& P2) {
    return Polynomial<T1>(single).coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator==(const Polynomial<T2>& P2, const T1& single) {
    return Polynomial<T1>(single).coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const Polynomial<T1>& P1, const Polynomial<T2>& P2) {
    return P1.coeffs != P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const T1& single, const Polynomial<T2>& P2) {
    return Polynomial<T1>(single).coeffs != P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const Polynomial<T2>& P2, const T1& single) {
    return Polynomial<T1>(single).coeffs != P2.coeffs;
}