统计

留言簿(1)

DB

Others

QA

Tech Website

阅读排行榜

评论排行榜

打印全排列

在《组合数学》里面全排列是一个常见的问题。
描述如下:有x1,x2,x3,...xn,共n个元素,打印出它的全排列。
如:1 , 2 , 3
有6种排列: 123, 132, 213, 231, 312, 321
思路: 元素的全排列,其实就是遍列全部元素组成的一个排列树,用回溯法可以得到比较好的效率,特别是空间上,,由于遍列整棵树,时间复杂度为O(n!)

 1 /** 
 2  *  打印出list[k,m]的全排列 
 3  * @param list 
 4  * @param k  beginning index 
 5  * @param m  finishing index 
 6  */  
 7 static void getPerm(Object[] list, int k , int m){  
 8     if( k == m){  
 9         for(int i = 0; i <= m; i++)  
10             System.out.print(list[i]);  
11         System.out.println();  
12     }else  
13         forint i = k; i <= m; i++){  
14         MyMath.swap(list, i, k);  
15         getPerm(list, k+1, m);  
16         MyMath.swap(list, i, k);  
17           
18     }  
19 }  


 引申:类似此种算法的还有就是打印字符串(如:ABC)的真子集,其核心算法还是一样的

 

posted on 2010-11-21 00:27 XXXXXX 阅读(500) 评论(0)  编辑  收藏 所属分类: Algorithm


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


网站导航: