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