一个计算机相关专业的大学新生，经过一个学期的洗礼，在学习了《c语言程序设计》的课程之后，对计算机有个懵懂的概念。同时，另外一门课程《线性代数》也按部就班的进行着，数学在那时还是他擅长并喜爱的，但习题中枯燥的数字矩阵计算彻底摧毁了他的底线，尤其是计算n阶行列式(尤其是n>3时)的值的时候，一次次错误的计算结果让他萌生了用计算机代替解题的想法，于是乎他安静的坐在电脑前开始思考合适的算法和方案。感叹他此时还不知道有全能的Google，经过短暂的思考，他找到了一个方便计算机实现的公式：
(其中sgn(σ)是排列σ的符号差)
先算乘再求和，如此枯燥的计算对计算机来说最拿手了，剩下的问题就是搞定这个σ，其实看上去神秘，说起来大家都明白，利用这个公式计算行列式的值核心的部分就是生成n的全排列，然后把每个排列的乘积加(减)起来。问题的核心已经明了，就是如何根据n生成全排列。当时的他不懂递归，不懂算法，更加不懂Google，懂的只有刚刚学会的一点点c的基本语法，甚至连指针都玩不明白，但是没关系，他懂数学，他觉得这就够了，于是经过数天的冥思苦想，他写出了下面的代码(部分截取，已经转换成C#)
1: public int[,] Pn(int n)
2: {
3: int[,] a = new int[GetFactorial(n), n];
4: for (var k = 0; k < n; k++)
5: {
6: for (int i = 0, length = GetFactorial(k + 1); i < length; i++)
7: {
8: a[i, k] = k;
9: }
10: for (int i = GetFactorial(k), s = i, length = GetFactorial(k + 1); i < length; i++)
11: {
12: int m = i - s;
13: int p = m / k;
14: int q = m % k;
15: for (int j = 0; j < k + 1; j++)
16: a[i, j] = (a[p, j] + q + 1) % (k + 1);
17: }
18: }
19: return a;
20: }
其中GetFactorial(n)是计算n!(n的阶乘)的函数，代码就不贴了，反正没用递归来计算阶乘。
相信大家对全排列问题并不陌生，在网上可以Google一大把实现，各种语言和各种算法的版本，这些算法无论是递归的实现还是非递归的实现都是基于一个核心运算，那就是“交换”，并且这些全排列算法都是一个一个“有序”生成的，而这段代码是纵向(乱序)填充出来的，而且全部的序列是通过“计算”而非“交换”得来的，加、减、除和取模，从严格意义上讲，虽然代码中没有递归，但每次计算都利用之前生成的数字再次计算，也算是借鉴递归的思想吧。然而这些都不重要，重要的是故事的主人公是8年前的我，而8年后的我在翻出这段代码的时候竟然不知道从前的自己是如何写出来的，因为我到现在还没想起来当时是如何思考的，这真的是我写的吗？代码的原始版本(c版本)没有注释，甚至没有缩进，变量命名也是现在的i,j,k,a,m,p,q…
由于最近有一个地方用到了全排列，就把当年的代码翻出来了，没想到是这个结果。起初我还试图在上面改进一下，把它变成可以一个一个顺序生成的，在努力了几个小时后我放弃了，因为实在想不起来当初是怎么想的了。既然想不起来就测试一下性能吧，因为这段代码只能生成序列的索引排列，而且由于是纵向生成的要一起申请内存，所以应用起来有一定的局限性，我们知道n的全排列的个数是n!个，当n变大的时候，生成时间会大幅提高，传统的递归方式在n到达一定大小时性能会急剧下降(不仅仅因为数量还因为深度递归)，而该算法却意外的很“稳定”，当n较小时(我的机器上测试n<7)，它没有递归快，但当n再变大的时候，它的优势就体现出来了，表现出优于递归的良好性能，当n再变的更大的时候，内存overflow了-_-!
总结一下，这个故事给我们三个启示(欢迎大家补充)：
一是对于理解上复杂的代码一定要写注释，方便别人阅读，更何况这个别人可能就是自己；
二是一定要花点时间在变量的名字上，否则后患无穷，对自己好点吧；
三是不要相信自己的大脑跟电脑一样，什么都记得，尤其是一些灵机一动的思路或灵感，动手记下来吧，像我现在在做的事情一样。
最后，善待你的代码，这等于在帮助未来的自己。
最后的最后，谁能帮忙解释下这段代码的数学原理:)
喜欢 
顶
难过
囧
围观
无聊
