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

關鍵字：全排列 Java JUnit 測試驅動開發(fā) 泛化

首先寫個測試

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

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

編譯通過，測試通過。

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

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

重構代碼。

 

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

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

 

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

修改測試代碼

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

 

獲取排列中的元素

在測試testArrange中加入代碼：

Ctrl + 1 。并改之。

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

增加測試用例

 

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

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

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

 

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

注意：當時為了方便，把測試類命名為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)用這個方法，如果是Arrangement<?>就不能調(diào)用。因為element的類型為?，無法把一個對象傳給？類型的參數(shù)。

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

 

任務列表：

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

 

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

6=3！只要有個求階乘的函數(shù)，就可以了。因為對求階乘的方法，我很熟悉，我認為我不會寫錯，就沒寫測試了。

 

AllArrange應該實現(xiàn)Iterable接口。

寫測試。

Arrangement的判等

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

元素順序沒有錯。增加equals方法。

判等要考慮的有兩個：

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

 

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

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

hasNext

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

測試

這里用到了自動裝箱。

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

增加測試用例

 

next

21354的下一個是21435

步驟：

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

 

找到5

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

 

找到4

交換34

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

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

 

next

測試

保證原Arrangement不變

 

TestAllArrangement

 

還有：

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

 

代碼缺少的還有注釋。

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