C++求行列式（满足一般性的解法）

突发奇想对y总的模板进行如下应用，如有不当，还望斧正

由行列式的定义,不同行不同列的n个元素的乘积，当这个乘积列的下标的逆序对个数为偶数时，该项为正，当这个乘积列的下标的逆序对个数为奇数时，该项为负,那么我们需要写一个函数来求出这些数的逆序对个数。

int merge_sort(int l,int r)
{
    if(l >= r) return 0;// 先判断区间左右端点是否合理
    int mid = l + r >> 1;  
    int i = l ,j = mid + 1,k = 0; 
    int res = merge_sort(l,mid) + merge_sort(mid + 1,r);//先递归左右两个区间排好序并求出各自区间的逆序对数量
    while (i <= mid && j <= r)//指针不超过范围
    if(a[i] <= a[j] ) temp[k++] = a[i++]; //左区间小的存入临时数组
    else{
        temp[k++] = a[j++]; //右区间小的存入临时数组
        res += mid - i + 1; //此时存在逆序对，a[i]>a[j] ,即a[i~mid]>a[j] ,逆序对数量为mid-i+1
    }       //与此同时，有一个区间已经遍历完毕且这区间的逆序对数量已经全部求出，下面进行扫尾
    while(i <= mid) temp[k++] = a[i++]; //扫尾，若左区间有剩余，依次存入临时数组
    while(j <= r) temp[k++] = a[j++];   //扫尾，若右区间有剩余，依次存入临时数组
    for(int i = l,k = 0;i <= r;i++,k++)     // 将临时数组的内容赋给原数组
    a[i] = temp[k];
    return res;
} 

这是归并排序的应用，在排好序的同时求出其中的逆序对数量

接下来就是求不同行不同列的n个元素,这里就需要用到DFS深度优先遍历来求出所有可能的情况,

从第一行开始列出该行可以存在的列数,第二行列出除第一行外的所有列数,以此类推,可以

求出所有的排列(类似于不需要满足对角线与反对角线条件的N皇后问题)

void dfs(int u) 
{
    if(u == n) 
    {
       ........
    }
    for(int i = 1;i <= n; i ++) //对于第u层对1~n这些数依次遍历
    {   
        if(!st[i])   //如果第u层的数i没有被用过,那么
        {
            a[u] = i;//第u个数就是i
            st[i] = true;//更新此时的i是被用过的状态
            dfs(u + 1);  //那么对u+1层进行上述操作
            st[i] = false; //当u+1层及其下面的层都进行过上述操作之后,恢复数i的状态
        }
    }
}

通过上述分析可得，用DFS来求出所有的行列组合并进行求积,对所例举出来的列数求其逆序对的个数,如果模2为1则需要加上负号,在对这些积求和即可求出一般情况下的行类似的值

if(u == n)
    {
        int sy = 1;//每列一种情况乘积就必须初始化为1,否则sy依然为上一种情况的积对后续结果会产生影响
        for(int i = 0;i < n ; i++)
        {
            sy *= g[i][a[i] - 1];//存放不同行列的积
        }
        ++z;
       if(merge_sort(0,n-1) % 2 == 1) sy = -sy;//判断这种排列的逆序对数,从而进行符号的判断
           /*  该行存在错误,该判断会影响了全排列的结果,若删除该行则不会对全排列的结果产生影响,但就无法判断符号 */
            sum[z] = sy + sum[z-1];//sum[z]依次存储各式之并取最后一次的运算结果为最终结果
    }

如果是这样，那么运算结果就出现了偏差。笔者在初次编写时就遇到了该问题,在将所有的操作显示出来后发现，merge_sort该函数对所应该产生的排列情况产生了影响，从而对乘积的正负号产生影响。如图所示

在进行分析后可以发现由于merge_sort函数在求逆序对数量的同时将该数组排好了序以至于对后面的排列情况产生了影响(虽然merge_sort改变了原来数组的顺序,但是其时间复杂度为O(n * log n)比暴力做法快不少),如果需要解决这个问题,那么我们需要用一个数组b来暂存排列好的情况,再对其用merge_sort求逆序对数量，求完后需要将数组b再赋值给原来的排列情况。 

综上所述，源代码如下

#include <iostream>
using namespace std;
const int N = 10;
bool st[N];//用于存储1~n这些数是否被用过
int n;
int a[N],temp[N]; //创建一个临时数组来存放
int g[N][N];
int merge_sort(int l,int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    int i = l ,j = mid + 1,k = 0;
    int res = merge_sort(l,mid) + merge_sort(mid + 1,r);//先递归左右两个区间排好序
    while (i <= mid && j <= r)
    if(a[i] <= a[j] ) temp[k++] = a[i++];
    else{
        temp[k++] = a[j++];
        res += mid - i + 1;
    }
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];
    for(int i = l,k = 0;i <= r;i++,k++)
    a[i] = temp[k];
    return res;
} 
int sum[N * N * N],z = 0; 
int b[N];//用来存储原先的排列顺序
void dfs(int u)
{
    if(u == n)
    {
        int sy = 1;
        for(int i = 0;i < n ; i++)
        {
           //printf("%d ",a[i]);
            sy *= g[i][a[i] - 1];//存放不同行列的积
            b[i] = a[i];
        }
        ++z;
        int res = merge_sort(0,n-1);
        //printf("%d ",res);
        for(int i = 0;i < n;i++)
        {
            a[i] = b[i];
        }
       if(res % 2 == 1) sy = -sy;//判断这种排列的逆序对数,从而进行符号的判断
        //  printf("%d\n",sy); 
           sum[z] = sy + sum[z-1];//sum[z]依次存储各式之和取最后一次的运算结果为最终结果
    }
    for (int i = 1;i <= n;i++)
    {
        if(!st[i])
        {
            a[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
    for(int j = 0;j < n;j++)
    scanf("%d",&g[i][j]);
    dfs(0);
    printf("%d",sum[z]);
}

输入测试

三阶：

 范德蒙德行列式：

          特别的如果行列式的阶数大于6,则需要将源代码中的sum数组的长度改大