우순열 기순열을 이용하여 정사각행렬의 행렬식을 계산하는 C++ 언어 소스

정리 (정사각행렬의 행렬식, derterminant)

n × n 행렬 A = \big( a_{ij} \big) 의 행렬식 \det(A) 는 다음 식과 같다

         \det(A) \ = \ \sum_{\sigma} \, \textrm{sign}(\sigma) \, a_{1 \sigma(1)} a_{2 \sigma(2)} \cdots a_{n \sigma(n)}

위에서 합은 집합 \{ 1, 2, \cdots, n \} 위에서의 모든 순열 \sigma에 관한 합이며, \textrm{sign}(\sigma) 는 \sigma가 우순열인 경우에는 +1이고, 기순열인 경우에는 -1이다.

 

다음의 C++ 언어로 작성된 소스는 순열을 출력하는 소스를 수정아여 정사각행렬의 행렬식을 계산하도록 하였다.

컴파일은 g++ 또는 Visual C++ 의 명령줄 컴파일러 cl 을 이용한다.

 

// Filename: determinant-03.cpp
//
// Compile: g++ -std=c++11 -o determinant-03 determinant-03.cpp
// Execute: ./determinant-03 [integer]
//
//     or
//
// Compile: cl /EHsc determinant-03.cpp
// Execute: determinant-03 [integer]
//
// Date: 2013. 9. 20.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>

using namespace std;

template<typename T>
class Array2D
{
    private:
        const int width;
        T * data;
    public:
        T& operator() (int x, int y) { return data[y*width + x]; }
        Array2D(const int w, const int h) : width(w) { data = new T[w*h]; }
        ~Array2D() { delete [] data; }
};

void printPermutation(const vector<int> pmt, int counter)
{
    int n = pmt.size();
    cout << "[";
    if (n > 0)
    {
        cout << " " << pmt[0];
        if (n > 1)
        {
            for (int i = 1; i < n; i++)
            {
                cout << ", " << pmt[i];
            }
        }
        cout << " ";
    }
    cout << "]";
    if ((counter % 2) == 0)
        cout << "    -- even --";
    else
        cout << "    -- odd  --";
    cout << endl;
}

void swap(vector<int> &pmt, int i, int j)
{
    int x = pmt[j];
    pmt[j] = pmt[i];
    pmt[i] = x;
}

void printMatrix(Array2D<double> &mat, int nrow, int ncol)
{
    for (int i = 0; i < nrow; i++)
    {
        cout << "[[";
        for (int j = 0; j < ncol; j++)
        {
            cout << " " << setw(9) << mat(i, j) << " ";
        }
        cout << "  ]]" << endl;
    }
    cout << endl;
}

#include <sstream>
void readMatrix(Array2D<double> &mat, int nrow, int ncol)
{
  std::string line;
     double x;
     int i = 0;
     while (i < nrow*ncol)
     {
          cin >> line;
          std::istringstream iss(line);
          while (iss)
          {
              std::string sub;
              iss >> sub;

              std::istringstream ins(sub);
              if (!(ins >> x))
                  break;
              mat(i / ncol, i % ncol) = x;
              i++;
          }
     }
}

void doPermute(Array2D<double> &mat, int dim, vector<int> pmt, int size, int &cnt, double &det, bool show_flag)
{
    double x;
    double y;
    if (size == 2)
    {
       if (show_flag)
            printPermutation(pmt, cnt);
        x = 1.0;
        for (int j = 0; j < dim; j++)
        {
         if (mat(j, pmt[j]) == 0) {
          x = 0;
          break;
         }
         x *= mat(j, pmt[j]);
        }
        det += ((cnt % 2) == 0) ? x : -x;
        swap(pmt, 0, 1);
        cnt++;
        if (show_flag)
            printPermutation(pmt, cnt);
        x = 1.0;
        for (int j = 0; j < dim; j++)
        {
           if (mat(j, pmt[j]) == 0) {
          x = 0.0;
          break;
         }
        x *= mat(j, pmt[j]);
        }
        det += ((cnt % 2) == 0) ? x : -x;
        swap(pmt, 0, 1);
        cnt--;
    }
    else if (size > 2)
    {
        doPermute(mat, dim, pmt, size - 1, cnt, det, show_flag);
        for (int i = size - 2; i >= 0; i--)
        {
             swap(pmt, i, size - 1);
             cnt++;
             doPermute(mat, dim, pmt, size - 1, cnt, det, show_flag);
        }
        for (int i = 0; i <= size - 2; i++)
        {
            swap(pmt, i, size - 1);
            cnt--;
        }
    }
}

int main(int argc, const char *argv[])
{
    // vector<int> v = { 0, 1, 2, 3, 4 };     // syntax for C++11
    vector<int> v(5);
    for (int i = 0; i < 5; i++)
    {
     v[i] = i;
    }
   
    int counter = 0;
    int dim = 3;
    int k = 3;
    double d = 0.0;

    if (argc > 1)
    {
        sscanf(argv[1], "%d", &k);
    }

    if (k > 5)
    {
        for (int i = 5; i < k; i++)
        {
            v.push_back(i);
        }
    }
    else if (k < 5) {
       for (int i = 0; i < 5 - k; i++)
       {
          v.pop_back();
       }
    }

    dim = k;
    Array2D<double> mat(dim, dim);

    cout << "Input a " << k << " by " << k << " matrix" << endl;

    readMatrix(mat, k, k);

    cout << endl;
    cout << "The given matrix is " << endl;
    printMatrix(mat, dim, dim);
   
    bool show_flag = false;
    doPermute(mat, dim, v, k, counter, d, show_flag);

    if (show_flag)
        cout << endl;
    cout << "Its determinant is " << d << "." << endl;
    return 0;
}

/*
Execute & Output:
명령프롬프트> determinant-03
Input a 3 by 3 matrix
1 2 3   4 5 6.02   7 8.1   9

The given matrix is
[[         1          2          3   ]]
[[         4          5       6.02   ]]
[[         7        8.1          9   ]]

Its determinant is 0.718.

명령프롬프트> determinant-03 2
Input a 2 by 2 matrix
7 8
0.1 5.1

The given matrix is
[[         7          8   ]]
[[       0.1        5.1   ]]

Its determinant is 34.9.

명령프롬프트> determinant-03 4
Input a 4 by 4 matrix
1 2 3   4 5 6.02   7 8.1   9
0 0 0 7 0 2 3

The given matrix is
[[         1          2          3          4   ]]
[[         5       6.02          7        8.1   ]]
[[         9          0          0          0   ]]
[[         7          0          2          3   ]]

Its determinant is 32.22.
*/