摘要：全排列是組合數(shù)學(xué)中的基本問題。求全排列有很多方法，比如：遞歸算法、字典順序法、遞增/遞減進(jìn)位制數(shù)法和鄰位對換法等。本文就在Java、JUnit4平臺(tái)中，采用測試驅(qū)動(dòng)開發(fā)方法，通過實(shí)現(xiàn)全排列，來學(xué)習(xí)Java SE 5中的泛化編程。

關(guān)鍵字：全排列 Java JUnit 測試驅(qū)動(dòng)開發(fā) 泛化

首先寫個(gè)測試

以最快的方式，通過編譯，并讓測試通過。

在eclipse中通過使用快捷鍵 Ctrl + 1 ，可以快速生成Stob。

編譯通過，測試通過。

發(fā)現(xiàn)問題：(task list）

• length方法中的6是怎么來的？
• 排列中的元素可不僅僅是String
• 排列中的元素個(gè)數(shù)，很有可能不是3個(gè)。
• 獲取排列中的元素

重構(gòu)代碼。

 

排列中的元素個(gè)數(shù)，很有可能不是3個(gè)。

采用了Java SE 5中最新的特性：可變參數(shù)。vararg。這樣可以傳入任意個(gè)元素，或一個(gè)元素?cái)?shù)組。然后，并重命名了參數(shù)。

 

排列中的元素可不僅僅是String

修改測試代碼

出現(xiàn)了編譯錯(cuò)誤。這次Ctrl + 1 不會(huì)自動(dòng)解決問題。修改Arrangement類。

 

獲取排列中的元素

在測試testArrange中加入代碼：

Ctrl + 1 。并改之。

測試失敗。加入字段。并改get方法和構(gòu)造函數(shù)。

增加測試用例

 

length方法中的6是怎么來的？

6表示：傳入3個(gè)元素，就有六種排列方式。再看看Arrangement類的職責(zé)？Arrangement表示的應(yīng)該是一個(gè)排列，而對于全排列來說，需要一個(gè)新的類來表示，取名為：AllArrangement。

所以修改測試，修改length方法。length方法返回的就是，elements.length。

 

還需要Arrangement類實(shí)現(xiàn)什么功能？暫時(shí)還不清楚，這最好問AllArrangement類。編寫AllArrangement類的測試。

注意：當(dāng)時(shí)為了方便，把測試類命名為TestArrange，現(xiàn)重命名為：TestArrangement。

 

AllArrangement

編寫測試

生成Stob類和方法

測試通過。

 

注意：Arrangement類型，由于沒使用泛型，編譯器出現(xiàn)了警告。Ctrl + 1 變?yōu)锳rrangement<?>,

Arrangement和Arrangement<?>有什么區(qū)別？

如果Arrangement類存在下面的方法：

public set(int index, E element) {...}

如果參數(shù)是Arrangement，就可以調(diào)用這個(gè)方法，如果是Arrangement<?>就不能調(diào)用。因?yàn)閑lement的類型為?，無法把一個(gè)對象傳給？類型的參數(shù)。

這個(gè)方法中，不需要更改Arrangement中的元素，取Arrangement<?>類型作為arrangement的參數(shù)，剛好。

 

任務(wù)列表：

• 如何求得全排列的元素個(gè)數(shù)？
• AllArrange應(yīng)該實(shí)現(xiàn)Iterable接口。

 

如何求得全排列的元素個(gè)數(shù)？

6=3！只要有個(gè)求階乘的函數(shù)，就可以了。因?yàn)閷η箅A乘的方法，我很熟悉，我認(rèn)為我不會(huì)寫錯(cuò)，就沒寫測試了。

 

AllArrange應(yīng)該實(shí)現(xiàn)Iterable接口。

寫測試。

Arrangement的判等

增加toString方法。toString只是用來更加直觀的顯示，沒必要測試。

元素順序沒有錯(cuò)。增加equals方法。

判等要考慮的有兩個(gè)：

• 與null對象判等
• 與非同類對象判等

 

再回到TestAllArrangement類。用字典順序法去迭代排列。

• hasNext == Arrangement.isNotMax
• next = Arrangement.next

hasNext

排列 54321(12345 五個(gè)元素的排列)是最大。

測試

這里用到了自動(dòng)裝箱。

改變了類型參數(shù)。

增加測試用例

 

next

21354的下一個(gè)是21435

步驟：

1. 找到5。從右往左，第一個(gè)大值
2. 找到4。從5開始往右，大于3的最小數(shù)
3. 交換3和4. 變成：21453
4. 把4右邊的元素排序。

 

找到5

isMax方法和lastTop方法很相似，更改isMax。

 

找到4

交換34

這里又用了一個(gè)新的類型變量T。由于這么簡單的函數(shù)，就不寫測試了。

排序，用Arrays.sort簡單解決。

 

next

測試

保證原Arrangement不變

 

TestAllArrangement

 

還有：

• Arrangement的個(gè)數(shù)不能太多
• Arrangement中的元素不能重復(fù)
• AllArrangement中的迭代器iterator應(yīng)該用Singleton(單例)模式
• 迭代器next方法返回的是Arrangement<?>
• remove方法

 

代碼缺少的還有注釋。

最終的源代碼下載地址：http://m.tkk7.com/Files/jeff-lau/arrangement.zip