一個計算機相關專業(yè)的大學新生，經(jīng)過一個學期的洗禮，在學習了《c語言程序設計》的課程之后，對計算機有個懵懂的概念。同時，另外一門課程《線性代數(shù)》也按部就班的進行著，數(shù)學在那時還是他擅長并喜愛的，但習題中枯燥的數(shù)字矩陣計算徹底摧毀了他的底線，尤其是計算n階行列式(尤其是n>3時)的值的時候，一次次錯誤的計算結果讓他萌生了用計算機代替解題的想法，于是乎他安靜的坐在電腦前開始思考合適的算法和方案。感嘆他此時還不知道有全能的Google，經(jīng)過短暫的思考，他找到了一個方便計算機實現(xiàn)的公式：
(其中sgn(σ)是排列σ的符號差)
先算乘再求和，如此枯燥的計算對計算機來說最拿手了，剩下的問題就是搞定這個σ，其實看上去神秘，說起來大家都明白，利用這個公式計算行列式的值核心的部分就是生成n的全排列，然后把每個排列的乘積加(減)起來。問題的核心已經(jīng)明了，就是如何根據(jù)n生成全排列。當時的他不懂遞歸，不懂算法，更加不懂Google，懂的只有剛剛學會的一點點c的基本語法，甚至連指針都玩不明白，但是沒關系，他懂數(shù)學，他覺得這就夠了，于是經(jīng)過數(shù)天的冥思苦想，他寫出了下面的代碼(部分截取，已經(jīng)轉換成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的階乘)的函數(shù)，代碼就不貼了，反正沒用遞歸來計算階乘。
相信大家對全排列問題并不陌生，在網(wǎng)上可以Google一大把實現(xiàn)，各種語言和各種算法的版本，這些算法無論是遞歸的實現(xiàn)還是非遞歸的實現(xiàn)都是基于一個核心運算，那就是“交換”，并且這些全排列算法都是一個一個“有序”生成的，而這段代碼是縱向(亂序)填充出來的，而且全部的序列是通過“計算”而非“交換”得來的，加、減、除和取模，從嚴格意義上講，雖然代碼中沒有遞歸，但每次計算都利用之前生成的數(shù)字再次計算，也算是借鑒遞歸的思想吧。然而這些都不重要，重要的是故事的主人公是8年前的我，而8年后的我在翻出這段代碼的時候竟然不知道從前的自己是如何寫出來的，因為我到現(xiàn)在還沒想起來當時是如何思考的，這真的是我寫的嗎？代碼的原始版本(c版本)沒有注釋，甚至沒有縮進，變量命名也是現(xiàn)在的i,j,k,a,m,p,q…
由于最近有一個地方用到了全排列，就把當年的代碼翻出來了，沒想到是這個結果。起初我還試圖在上面改進一下，把它變成可以一個一個順序生成的，在努力了幾個小時后我放棄了，因為實在想不起來當初是怎么想的了。既然想不起來就測試一下性能吧，因為這段代碼只能生成序列的索引排列，而且由于是縱向生成的要一起申請內存，所以應用起來有一定的局限性，我們知道n的全排列的個數(shù)是n!個，當n變大的時候，生成時間會大幅提高，傳統(tǒng)的遞歸方式在n到達一定大小時性能會急劇下降(不僅僅因為數(shù)量還因為深度遞歸)，而該算法卻意外的很“穩(wěn)定”，當n較小時(我的機器上測試n<7)，它沒有遞歸快，但當n再變大的時候，它的優(yōu)勢就體現(xiàn)出來了，表現(xiàn)出優(yōu)于遞歸的良好性能，當n再變的更大的時候，內存overflow了-_-!
總結一下，這個故事給我們三個啟示(歡迎大家補充)：
一是對于理解上復雜的代碼一定要寫注釋，方便別人閱讀，更何況這個別人可能就是自己；
二是一定要花點時間在變量的名字上，否則后患無窮，對自己好點吧；
三是不要相信自己的大腦跟電腦一樣，什么都記得，尤其是一些靈機一動的思路或靈感，動手記下來吧，像我現(xiàn)在在做的事情一樣。
最后，善待你的代碼，這等于在幫助未來的自己。
最后的最后，誰能幫忙解釋下這段代碼的數(shù)學原理:)
喜歡 
頂
難過
囧
圍觀
無聊
