全排列解析
10 26, 2008 Linux
今天没什么事，以前在学校一直没弄清楚全排列的实现。花了点时间研究，总算搞清楚了整个过程。基本思路：设R={r1,r2,…,rn}是要进行排列的n个元素,Ri=R-{ri}.集X中元素的全排列记为Perm(X),(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳定义如下:
当n=1时,Perm(R)={r},r是集合R中唯一的元素.
当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),….(rn)Perm(Rn)构成
代码如下(采用的测试数据为{1, 2, 3, 4})：
