随笔-16  评论-50  文章-2  trackbacks-0

摘要:全排列是组合数学中的基本问题。求全排列有很多方法,比如:递归算法、字典顺序法、递增/递减进位制数法和邻位对换法等。本文就在Java、JUnit4平台中,采用测试驱动开发方法,通过实现全排列,来学习Java SE 5中的泛化编程。

关键字:全排列 Java JUnit 测试驱动开发 泛化

首先写个测试

image

以最快的方式,通过编译,并让测试通过。

在eclipse中通过使用快捷键 Ctrl + 1 ,可以快速生成Stob。

image

编译通过,测试通过。

发现问题:(task list)

  • length方法中的6是怎么来的?
  • 排列中的元素可不仅仅是String
  • 排列中的元素个数,很有可能不是3个。
  • 获取排列中的元素

重构代码。

 

排列中的元素个数,很有可能不是3个。

image

采用了Java SE 5中最新的特性:可变参数。vararg。这样可以传入任意个元素,或一个元素数组。然后,并重命名了参数。

 

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

修改测试代码

image

出现了编译错误。这次Ctrl + 1 不会自动解决问题。修改Arrangement类。

image

 

获取排列中的元素

在测试testArrange中加入代码:

image

Ctrl + 1 。并改之。

image

测试失败。加入字段。并改get方法和构造函数。

image

增加测试用例

image

 

length方法中的6是怎么来的?

6表示:传入3个元素,就有六种排列方式。再看看Arrangement类的职责?Arrangement表示的应该是一个排列,而对于全排列来说,需要一个新的类来表示,取名为:AllArrangement。

所以修改测试,修改length方法。length方法返回的就是,elements.length。

 

还需要Arrangement类实现什么功能?暂时还不清楚,这最好问AllArrangement类。编写AllArrangement类的测试。

注意:当时为了方便,把测试类命名为TestArrange,现重命名为:TestArrangement。

 

AllArrangement

编写测试

image

生成Stob类和方法

image

测试通过。

 

注意:Arrangement类型,由于没使用泛型,编译器出现了警告。Ctrl + 1 变为Arrangement<?>,

Arrangement和Arrangement<?>有什么区别?

如果Arrangement类存在下面的方法:

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

如果参数是Arrangement,就可以调用这个方法,如果是Arrangement<?>就不能调用。因为element的类型为?,无法把一个对象传给?类型的参数

这个方法中,不需要更改Arrangement中的元素,取Arrangement<?>类型作为arrangement的参数,刚好。

 

任务列表:

  • 如何求得全排列的元素个数?
  • AllArrange应该实现Iterable接口。

 

如何求得全排列的元素个数?

6=3!只要有个求阶乘的函数,就可以了。因为对求阶乘的方法,我很熟悉,我认为我不会写错,就没写测试了。

image

 

AllArrange应该实现Iterable接口。

写测试。

Arrangement的判等

image

image

增加toString方法。toString只是用来更加直观的显示,没必要测试。

image

image

元素顺序没有错。增加equals方法。

image

判等要考虑的有两个:

  • 与null对象判等
  • 与非同类对象判等

 

再回到TestAllArrangement类。用字典顺序法去迭代排列。

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

hasNext

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

测试

image

这里用到了自动装箱。

image

image

改变了类型参数。

增加测试用例

image

 

next

image

21354的下一个是21435

步骤:

  1. 找到5。从右往左,第一个大值
  2. 找到4。从5开始往右,大于3的最小数
  3. 交换3和4. 变成:21453
  4. 把4右边的元素排序。

 

找到5

image

image

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

image

 

找到4

image

image

交换34

image

这里又用了一个新的类型变量T。由于这么简单的函数,就不写测试了。

排序,用Arrays.sort简单解决。

 

next

测试

image

image

保证原Arrangement不变

 

TestAllArrangement

image

 

image

image

还有:

  • 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

只有注册用户登录后才能发表评论。


网站导航: