Java　排列組合的有趣算法
		
          
		1. 用1、2、3、4、5這五個數字，用java寫一個main函數，打印出所有不同的排列，如：51234、41235等。 

          Java代碼  收藏代碼
          1. public class TestQuestion {  
          2. static int[] bits = new int[] { 1, 2, 3, 4, 5 };  
          3.   
          4. /** 
          5. * @param args 
          6. */  
          7. public static void main(String[] args) {  
          8. sort("", bits);  
          9. }  
          10.   
          11. private static void sort(String prefix, int[] a) {  
          12. if (a.length == 1) {  
          13. System.out.println(prefix + a[0]);  
          14. }  
          15.   
          16. for (int i = 0; i < a.length; i++) {  
          17. sort(prefix + a[i], copy(a, i));  
          18. }  
          19. }  
          20.   
          21. private static int[] copy(int[] a,int index){  
          22. int[] b = new int[a.length-1];  
          23. System.arraycopy(a, 0, b, 0, index);  
          24. System.arraycopy(a, index+1, b, index, a.length-index-1);  
          25. return b;  
          26. }  
          27. }  


          2. 對第一題增加難度，用1、2、2、3、4、5這六個數字，用java寫一個main函數，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"與"5"不能相連。 

          基本思路： 
          2-1. 把問題歸結為圖結構的遍歷問題。圖遍歷思想：實際上6個數字就是六個結點，把六個結點連接成無向連通圖，對于每一個結點求這個圖形的遍歷路徑，所有結點的遍歷路徑就是最后對這6個數字的排列組合結果集。 

          2-2. 顯然這個結果集還未達到題目的要求。從以下幾個方面考慮：                                                 

              2-2-1.   3，5不能相連：實際要求這個連通圖的結點3，5之間不能連通, 可在構造圖結構時就滿足改條件，然后再遍歷圖。 
              2-2-2.   不能有重復: 考慮到有兩個2，明顯會存在重復結果，可以把結果集放在TreeSet中過濾重復結果 
              2-2-3.   4不能在第三位: 仍舊在結果集中去除滿足此條件的結果。 

          采用二維數組定義圖結構，最后的代碼是： 

          Java代碼  收藏代碼
          1. import java.util.Iterator;  
          2. import java.util.TreeSet;  
          3.   
          4. public class TestQuestion {  
          5.   
          6. private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};  
          7. private int n = b.length;  
          8. private boolean[] visited = new boolean[n];  
          9. private int[][] a = new int[n][n];  
          10. private String result = "";  
          11. private TreeSet set = new TreeSet();  
          12.   
          13. public static void main(String[] args) {  
          14. new TestQuestion().start();  
          15. }  
          16.   
          17. private void start() {  
          18.   
          19. // Initial the map a[][]  
          20. for (int i = 0; i < n; i++) {  
          21. for (int j = 0; j < n; j++) {  
          22. if (i == j) {  
          23. a[i][j] = 0;  
          24. } else {  
          25.     a[i][j] = 1;  
          26. }  
          27. }  
          28. }  
          29.   
          30. // 3 and 5 can not be the neighbor.  
          31. a[3][5] = 0;  
          32. a[5][3] = 0;  
          33.   
          34. // Begin to depth　search.  
          35. for (int i = 0; i < n; i++) {  
          36.     this.depthFirstSearch(i);  
          37. }  
          38.   
          39. // Print result treeset.  
          40. Iterator it = set.iterator();  
          41. while (it.hasNext()) {  
          42. String string = (String) it.next();  
          43. // "4" can not be the third position.  
          44. if (string.indexOf("4") != 2) {  
          45. System.out.println(string);  
          46. }  
          47. }  
          48. }  
          49.   
          50. private void depthFirstSearch(int startIndex) {  
          51. visited[startIndex] = true;  
          52. result = result + b[startIndex];  
          53. if (result.length() == n) {  
          54. // Filt the duplicate value.  
          55. set.add(result);  
          56. }  
          57. for(int j = 0; j < n; j++) {  
          58. if (a[startIndex][j] == 1 && visited[j] == false) {  
          59. depthFirstSearch(j);  
          60. } else {  
          61. continue;  
          62. }  
          63. }  
          64.   
          65. // restore the result value and visited value after listing a node.  
          66.     result = result.substring(0, result.length() -1);  
          67.     visited[startIndex] = false;  
          68. }  
          69. }  


          3.   遞歸思想。遞歸要抓住的關鍵是：（1）遞歸出口；（2）地推逐步向出口逼近。 

          3-1. 漢諾塔 

          　　這是遞歸的超經典的例子，幾乎每本程序設計書上談到遞歸都會介紹。具體情景不再贅述。以我上述的方法觀之： 

              3-1-1. 遞歸的出口在于disk數為一的時候 

              3-1-2. 向出口逼近：如果不是一，是n ，則我們先挪動上面n-1塊disk，等上面挪完，即遞歸返回的時候，我們挪動最底下的disk. 

          　　僅僅如此，一個貌似十分復雜的問題就解決了，因為挪動那n-1塊disk的時候，會繼續向上減少，直到disk的數量為一為止。下面給出代碼： 

          Java代碼  收藏代碼
          1. import javax.swing.JOptionPane;   
          2. public class Hanoi{   
          3. private static final String DISK_B = "diskB";   
          4. private static final String DISK_C = "diskC";   
          5. private static final String DISK_A = "diskA";   
          6. static String from=DISK_A;   
          7. static String to=DISK_C;   
          8. static String mid=DISK_B;   
          9. public static void main(String[] args) {   
          10. String input=JOptionPane.showInputDialog("please input the number of the disks you want me move.");   
          11. int num=Integer.parseInt(input);   
          12. move(num,from,mid,to);   
          13. }   
          14. private static void move(int num, String from2, String mid2, String to2) {   
          15. if(num==1){   
          16. System.out.println("move disk 1 from "+from2+" to "+to2);   
          17. }   
          18. else {   
          19. move(num-1,from2,to2,mid2);   
          20. System.out.println("move disk "+num+" from "+from2+" to "+to2);   
          21. move(num-1,mid2,from2,to2);   
          22. }   
          23. }   
          24. }  
          3-2. 這是一個排列的例子，它所做的工作是將輸入的一個字符串中的所有元素進行排序并輸出，例如：你給出的參數是"abc" 則程序會輸出： 

          abc 
          acb 
          bac 
          bca 
          cab 
          cba 

          分析： 

              3-2-1. 算法的出口在于：low＝high也就是現在給出的排列元素只有一個時； 

              3-2-2. 算法的逼近過程：先確定排列的第一位元素，也就是循環中ｉ所代表的元素，然后ｌｏｗ＋１開始減少排列元素，如此下去，直到low＝high。（暫未調通） 

          Java代碼  收藏代碼
          1. public static void permute（String str） {   
          2. 　　char[] strArray = str.toCharArray（）；   
          3. 　　permute（strArray， 0， strArray.length - 1）；   
          4. 　　}   
          5. 　　public static void permute（char[] list， int low， int high） {   
          6. 　　int i；   
          7. 　　if （low == high） {   
          8. 　　String cout = ""；   
          9. 　　for （i = 0； i <= high； i++）   
          10. 　　cout += list[i]；   
          11. 　　System.out.println（cout）；   
          12. 　　} else {   
          13. 　　for （i = low； i <= high； i++） {   
          14. 　　char temp = list[low]；   
          15. 　　list[low] = list[i]；   
          16. 　　list[i] = temp；   
          17. 　　permute（list， low + 1， high）；   
          18. 　　temp = list[low]；   
          19. 　　list[low] = list[i]；   
          20. 　　list[i] = temp；   
          21. 　　}   
          22. 　　}   
          23. 　　}  

          3-3. 這是一個組合的例子，與上述的例子相似，只是它所做的工作是，輸出所給字符串中制定數目的元素的組合種類。 

          分析： 

              3-3-1. 程序出口在于ｎ＝１，此時只要輸出目標數組的所有元素即可 

              3-3-2. 逼近過程，當ｎ＞１　的時候，我們先取第一個元素放入目標數組中，然后ｎ－１，如此下去，最后出來。

          Java代碼  收藏代碼
          1. import javax.swing.JOptionPane;   
          2. public class Combination {   
          3. /**  
          4. * @param args  
          5. */   
          6. public static void main(String[] args) {   
          7. String input = JOptionPane.showInputDialog("please input your String： ");   
          8. String numString = JOptionPane.showInputDialog("please input the number of your Combination： ");   
          9. int num = Integer.parseInt(numString);   
          10. Combine(input, num);   
          11. }   
          12. private static void Combine(String input, int num) {   
          13. char[] a = input.toCharArray();   
          14. String b = "";   
          15. Combine(a, num, b, 0, a.length);   
          16. }   
          17. private static void Combine(char[] a, int num, String b, int low, int high) {   
          18. if (num == 0) {   
          19. System.out.println(b);   
          20. } else {   
          21. for (int i = low; i < a.length; i++) {   
          22. b += a[i];   
          23. Combine(a, num - 1, b, i+1, a.length);   
          24. b=b.substring(0, b.length()-1);   
          25. }   
          26. }   
          27. }   
          28. }  
          
		
          
			posted on 2011-07-20 16:12 七孑 閱讀(14103) 評論(1)  編輯  收藏  所屬分類: 經典算法典藏 
		
          
	
          
	
	


	


          
	    
    


          

          評論
          
	
	
			
          
				# re: Java　排列組合的有趣算法
					
						2014-12-07 21:40
					
				zudaima
			
          
			
          
				java算法demo源代碼下載：http://zuidaima.com/share/k%E7%AE%97%E6%B3%95-p1-s1.htm  回復  更多評論
				  
			
          
		

          




          





          


          

	
          
		
          
				
		
	
		
          
		
		
          只有注冊用戶登錄后才能發表評論。
          
		
          
			
		
          
			
		
          
		
		
          
		


          

		          		
		
          
		
          			
		
		
		
		
          
		
          
		
		
          
		
          
			網站導航:
		
		
          
		
          
			


		
          	
		
          
			 
		
          
		
          
			
		
          
		
          
			
				
		
          		
	
          	

          



          

				
				

			
          
			
          
				
					
          
	
          
		
          <2014年12月>
          
	
          日一二三四五六
          30123456
          78910111213
          14151617181920
          21222324252627
          28293031123
          45678910
          

          

					

          導航
          

					

          統計
          
	
					
					

          常用鏈接
          


          留言簿(1)
          


		
          隨筆分類
          
		
				
			
	
		
          隨筆檔案
          
		
				
			
	
		
          文章分類
          
		
				
			
	
		
          文章檔案
          
		
				
			
	



          搜索
          



          最新評論
	
          

          
	
			
		

          


          閱讀排行榜
          



          評論排行榜
          


				
			
          
			
			
			
			
			 

	

    







          
        
	




主站蜘蛛池模板：
宜良县|
湖南省|
灌南县|
元谋县|
桐柏县|
沂南县|
于田县|
江安县|
兰州市|
扎赉特旗|
柘荣县|
开封市|
丁青县|
普陀区|
宜春市|
双辽市|
板桥市|
紫阳县|
苍溪县|
灵宝市|
安丘市|
尤溪县|
鄢陵县|
二手房|
桑植县|
兰西县|
怀安县|
蓝山县|
宜兰县|
龙岩市|
岐山县|
四子王旗|
台前县|
裕民县|
安达市|
焉耆|
江北区|
龙里县|
泾阳县|
聂拉木县|
安西县|