PermutationGen用来枚举{1,...,n}的所有全排列。
D类用来计算行列式，只能对数值进行计算。
代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace Determinant
{
class Program
{
static void Main(string[] args)
{
//Console.WriteLine(D.SwitchCount(new int[] { 3, 2, 5, 1, 4 }));//D.PermutationGen pg = new D.PermutationGen(4);
//pg.FastIteration = true;
//foreach (var p in pg)
//{
// Console.WriteLine(pg.PermutationToString(p));
//}
D d1 = new D(3);
d1.Data[0, 0] = 1;
d1.Data[0, 1] = 2;
d1.Data[0, 2] = -4;
d1.Data[1, 0] = -2;
d1.Data[1, 1] = 2;
d1.Data[1, 2] = 1;
d1.Data[2, 0] = -3;
d1.Data[2, 1] = 4;
d1.Data[2, 2] = -2;
Console.WriteLine(d1.Value);
D d2
= new D(2);
d2.Data[0, 0] = 3;
d2.Data[0, 1] = 12;
d2.Data[1, 0] = 2;
d2.Data[1, 1] = 1;
Console.WriteLine(d2.Value);
Console.ReadKey();
}
}public class D
{
/// <summary>
/// 计算1-n的一个全排列的逆序数
/// </summary>
/// <param name="permutation">a permutation of 1-permutation.Length</param>
/// <returns></returns>
public static int SwitchCount(int[] permutation)
{
int count = 0;
if (permutation == null || permutation.Length == 0) throw new ArgumentException("输入不能为空", "permutation");
if (permutation.Length == 1)
{
return 0;
}
for (int i = 0; i < permutation.Length; i++)
{
if (permutation[i] < 1 || permutation[i] > permutation.Length) throw new ArgumentException("只计算1-n的排列的逆序数");
}
for (int i = 0; i < permutation.Length; i++)
{
for (int j = i + 1; j < permutation.Length; j++)
{
if (permutation[i] > permutation[j]) count++;
else if (permutation[i] == permutation[j]) throw new ArgumentException(String.Format("数字{0}重复出现在位置{1}和{2}", permutation[i], i, j), "permutation");
}
}
return count;
}double[,] data;
int n;
PermutationGen pg;public D(int rank)
{
if (rank < 2) throw new ArgumentException("Rank is at least 2.");
n = rank;
data = new double[rank, rank];
data.Initialize();
}public double[,] Data
{
get
{
return data;
}
}public double Value //calculate the value form the data given
{
get
{
double v = 0;
if (pg == null)
{
pg = new PermutationGen(n);
}foreach (var p in pg)
{
double u = 1;
for (int i = 0; i < n; i++)
{ //固定行，选列
u *= data[i, p[i] - 1];
}
u *= ((SwitchCount(p) & 1) == 1 ? -1 : 1);
v += u;
}return v;
}
}public class PermutationGen : IEnumerable<int[]>
{
int[] p, t, f;
int len;
StringBuilder pString;public bool ReturnNewPermutation
{
get;
set;
}public bool FastIteration
{
get;
set;
}public PermutationGen(int length)
{
len = length;
p = new int[length];
t = new int[length];//尚未被使用的数字
f = new int[length + 1];
for (int i = len; i >= 0; i--) //最前面两个元素不用
{
f[i] = Factorial(i);
}
}public int Count
{
get
{
return f[len];
}
}/// <summary>
///
/// </summary>
/// <param name="id">1至len</param>
/// <returns></returns>
public int[] GetPermutation(int id)
{
if (id >= f[len] || id < 0) throw new ArgumentException("1<=id<=len!");
for (int i = 0; i < len; i++) //所有数字都未被使用
{
t[i] = i + 1;
}int r, n, m = id;
for (int i = 0; i < len; i++)
{
n = Math.DivRem(m, f[len - i - 1], out r);
p[i] = GetUnusedNumberN(n + 1);
m = r;
}
return p;
}public string PermutationToString(int[] p)
{
int len = p.Length;
if (pString == null)
{
pString = new StringBuilder(len * 3);
}
pString.Length = 0;
pString.Append(p[0]);
for (int i = 1; i < len; i++)
{
pString.Append(",");
pString.Append(p[i]);
}return pString.ToString();
}
public string GetPermutationString()
{
return PermutationToString(p);
}public static int Factorial(int n)
{
int result = 1;
for (int i = n; i > 1; i--)
{
result *= i;
}
return result;
}/// <summary>
/// 返回第n个未被使用的元素
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
int GetUnusedNumberN(int n)
{
int count = 0;
for (int i = 0; i < len; i++)
{
if (t[i] != 0)
{
count++;
if (count == n)
{
int q = t[i];
t[i] = 0;//返回即被使用
return q;
}
}
}return 0;//没有足够的剩余元素
}/// <summary>
/// return the smallest positive integer that is not included in the n elements of array starting for start
/// </summary>
int GetNextSmallest(int[] array, int start, int n, int searchStart)
{
int i;
for (i = searchStart; i <= searchStart + n; i++)
{
int j;
for (j = start; j < n; j++)
{
if (array[j] == i) break;
}
if (j == n)
{
return i;
}
}
return 0; //impossible, but required by grammar
}#region IEnumerable<int[]> 成员public IEnumerator<int[]> GetEnumerator()
{
if (FastIteration)
{
for (int i = 0; i < len; i++)
{
p[i] = i + 1;
}for (int i = 0; i < f[len] - 1; i++)//返回第0号到倒数第二个排列
{
yield return ReturnNewPermutation ? p.Clone() as int[] : p;
//每次迭代构造下次应当返回的排列
for (int j = len - 1; j > 0; j--)
{
if (i / f[j] != (i + 1) / f[j])
{
//set p at level j
int k = len - j - 1;//convert to p index
p[k] = GetNextSmallest(p, 0, k, p[k] + 1);
k++;
while (k < len)
{
p[k] = GetNextSmallest(p, 0, k, 1);
k++;
}
break;
}
}
}
yield return ReturnNewPermutation ? p.Clone() as int[] : p;
}
else
{
if (ReturnNewPermutation)
{
for (int i = 0; i < f[len]; i++)
{
yield return GetPermutation(i).Clone() as int[];
}
}
else
{
for (int i = 0; i < f[len]; i++)
{
yield return GetPermutation(i);
}
}
}
}#endregion#region IEnumerable 成员 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}#endregion
}
}
}
