C 語言實現 n 階行列式計算：全排列遞迴法與代碼詳解

行列式是線性代數核心概念，程式計算常用**全排列展開定義式**：det(A) = Σ sign(σ) * Π a[i][σ(i)]。本文提供基於遞迴生成全排列的完整 C 實作，並詳解關鍵函數邏輯。

演算法原理

• 對 n×n 矩陣，共有 n! 項排列。
• 遞迴生成列索引排列 `perm[0..n-1]`，每個排列對應一項乘積。
• 計算排列逆序數決定正負號 (偶排列 +，奇排列 -)。
• 累加所有項得到行列式值。

代碼結構

#include <stdio.h>
#include <stdlib.h>

double **a;      // 矩陣指標陣列
int *perm;       // 當前排列
int n;           // 階數
double det = 0;  // 累加器

void swap(int *x, int *y) { int t=*x; *x=*y; *y=t; }

// 遞迴生成全排列並計算
void permute(int k) {
    if (k == n) {
        // 計算符號
        int inv = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if (perm[i] > perm[j]) inv++;
        double term = (inv % 2 == 0) ? 1 : -1;
        for (int i = 0; i < n; i++) term *= a[i][perm[i]];
        det += term;
        return;
    }
    for (int i = k; i < n; i++) {
        swap(&perm[k], &perm[i]);
        permute(k + 1);
        swap(&perm[k], &perm[i]); // 回溯
    }
}

int main() {
    scanf("%d", &n);
    a = malloc(n * sizeof(double*));
    for (int i = 0; i < n; i++) {
        a[i] = malloc(n * sizeof(double));
        for (int j = 0; j < n; j++) scanf("%lf", &a[i][j]);
    }
    perm = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) perm[i] = i;
    permute(0);
    printf("Determinant = %lf\n", det);
    // 釋放記憶體...
    return 0;
}

關鍵點解析

1. swap + 遞迴 + 回溯：經典全排列生成模板，原地交換，空間 O(n)。
2. 逆序數計算：O(n²) 簡單可靠，n ≤ 10 時可接受。大矩陣應改用 **LU 分解** (O(n³)) 或 **高斯消去法**。
3. 雙精度 `double` 存儲矩陣元素與結果，減少誤差。
4. 動態分配二維陣列：指標陣列 + 每行獨立 `malloc`，便於釋放。

測試範例

輸入:
3
1 2 3
4 5 6
7 8 9
輸出:
Determinant = 0.000000  (第三行 = 2*第二行 - 第一行，行列式為 0)

效能與改進方向

本代碼適合教學演示、小階數驗證。實際工程請使用成熟線性代數庫 (Eigen, Armadillo, MKL, OpenBLAS) 以獲得數值穩定性與高效能。