摘要:全排列是组合数学中的基本问题。求全排列有很多方法,比如:递归算法、字典顺序法、递增/递减进位制数法和邻位对换法等。本文就在Java、JUnit4平台中,采用测试驱动开发方法,通过实现全排列,来学习Java SE 5中的泛化编程。
关键字:全排列 Java JUnit 测试驱动开发 泛化
首先写个测试
以最快的方式,通过编译,并让测试通过。
在eclipse中通过使用快捷键 Ctrl + 1 ,可以快速生成Stob。
编译通过,测试通过。
发现问题:(task list)
- length方法中的6是怎么来的?
- 排列中的元素可不仅仅是String
- 排列中的元素个数,很有可能不是3个。
- 获取排列中的元素
重构代码。
排列中的元素个数,很有可能不是3个。
采用了Java SE 5中最新的特性:可变参数。vararg。这样可以传入任意个元素,或一个元素数组。然后,并重命名了参数。
排列中的元素可不仅仅是String
修改测试代码
出现了编译错误。这次Ctrl + 1 不会自动解决问题。修改Arrangement类。
获取排列中的元素
在测试testArrange中加入代码:
Ctrl + 1 。并改之。
测试失败。加入字段。并改get方法和构造函数。
增加测试用例
length方法中的6是怎么来的?
6表示:传入3个元素,就有六种排列方式。再看看Arrangement类的职责?Arrangement表示的应该是一个排列,而对于全排列来说,需要一个新的类来表示,取名为:AllArrangement。
所以修改测试,修改length方法。length方法返回的就是,elements.length。
还需要Arrangement类实现什么功能?暂时还不清楚,这最好问AllArrangement类。编写AllArrangement类的测试。
注意:当时为了方便,把测试类命名为TestArrange,现重命名为:TestArrangement。
AllArrangement
编写测试
生成Stob类和方法
测试通过。
注意:Arrangement类型,由于没使用泛型,编译器出现了警告。Ctrl + 1 变为Arrangement<?>,
Arrangement和Arrangement<?>有什么区别?
如果Arrangement类存在下面的方法:
public set(int index, E element) {...}
如果参数是Arrangement,就可以调用这个方法,如果是Arrangement<?>就不能调用。因为element的类型为?,无法把一个对象传给?类型的参数。
这个方法中,不需要更改Arrangement中的元素,取Arrangement<?>类型作为arrangement的参数,刚好。
任务列表:
- 如何求得全排列的元素个数?
- AllArrange应该实现Iterable接口。
如何求得全排列的元素个数?
6=3!只要有个求阶乘的函数,就可以了。因为对求阶乘的方法,我很熟悉,我认为我不会写错,就没写测试了。
AllArrange应该实现Iterable接口。
写测试。
Arrangement的判等
增加toString方法。toString只是用来更加直观的显示,没必要测试。
元素顺序没有错。增加equals方法。
判等要考虑的有两个:
再回到TestAllArrangement类。用字典顺序法去迭代排列。
- hasNext == Arrangement.isNotMax
- next = Arrangement.next
hasNext
排列 54321(12345 五个元素的排列)是最大。
测试
这里用到了自动装箱。
改变了类型参数。
增加测试用例
next
21354的下一个是21435
步骤:
- 找到5。从右往左,第一个大值
- 找到4。从5开始往右,大于3的最小数
- 交换3和4. 变成:21453
- 把4右边的元素排序。
找到5
isMax方法和lastTop方法很相似,更改isMax。
找到4
交换34
这里又用了一个新的类型变量T。由于这么简单的函数,就不写测试了。
排序,用Arrays.sort简单解决。
next
测试
保证原Arrangement不变
TestAllArrangement
还有:
- Arrangement的个数不能太多
- Arrangement中的元素不能重复
- AllArrangement中的迭代器iterator应该用Singleton(单例)模式
- 迭代器next方法返回的是Arrangement<?>
- remove方法
代码缺少的还有注释。
最终的源代码下载地址:http://www.blogjava.net/Files/jeff-lau/arrangement.zip
posted on 2008-01-03 01:58
Jeff Lau 阅读(1857)
评论(0) 编辑 收藏 所属分类:
Jeff On Java 2008