两种方法-用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412325等.要求："4"不能在第三位 - 代码物语-Let code talk - ITeye技术网站

两种方法-用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412325等.要求："4"不能在第三位 - 代码物语-Let code talk - ITeye技术网站

1.      * 题目:用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412325等. 
2.      * 要求："4"不能在第三位，"3"与"5"不能相连 
3.      * A(6,6)-A(5,5)-2*5*A(4,4)+2*3*A(3,3)=396,396/2=198 
4.      * two solutions: 
5.      * 1.Permutation 
6.      * 2.Graph,depthFirst 

1. public class Graph {  
2.     private static final int[] DATA={1,2,2,3,4,5};  
3.     private static final int LENGTH=DATA.length;  
4.     private boolean[] visited;  
5.     private int[][] matrix;  
6.     private StringBuilder resultString;  
7.     private Set<String> resultSet;//use 'Set' to reject duplicate string.  
8.       
9.     public static void main(String[] args) {  
10.         Graph graph=new Graph();  
11.         graph.initial();  
12.         for(int i=0;i<LENGTH;i++){  
13.             graph.depthFirst(i);//start from 1,2,2,3,4,5,find their corresponding DFS  
14.         }  
15.         graph.print();  
16.     }  
17.   
18.     public void initial(){  
19.         resultString=new StringBuilder();  
20.         resultSet=new HashSet<String>();  
21.         int n=LENGTH;  
22.         visited=new boolean[n];  
23.         matrix=new int[n][n];  
24.         for(int i=0;i<n;i++){  
25.             for(int j=0;j<n;j++){  
26.                 if(i==j){  
27.                     matrix[i][j]=0;  
28.                 }else{  
29.                     matrix[i][j]=1;  
30.                 }  
31.             }  
32.         }  
33.         //"3"与"5"不能相连  
34.         matrix[3][5]=0;  
35.         matrix[5][3]=0;  
36.     }  
37.       
38.     public void depthFirst(int origin){  
39.         //case 1.resultString includes DATA[origin]  
40.         resultString.append(DATA[origin]);  
41.         visited[origin]=true;  
42.         if(resultString.length()==LENGTH){  
43.             boolean ok=resultString.charAt(2)!='4';//"4"不能在第三位  
44.             if(ok){  
45.                 resultSet.add(resultString.toString());  
46.             }  
47.         }  
48.         for(int i=0;i<LENGTH;i++){  
49.             if(!visited[i]&&matrix[origin][i]==1){  
50.                 depthFirst(i);  
51.             }else{  
52.                 continue;  
53.             }  
54.         }  
55.         //case 2.resultString don't include DATA[origin]  
56.         resultString.deleteCharAt(resultString.length()-1);//remove DATA[origin]  
57.         visited[origin]=false;  
58.     }  
59. }  

1. public class Perm {  
2.     public static final int BAD_INDEX = 3;  
3.     public static final int BAD_VALUE = 4;  
4.     public static final int FIRST_VALUE = 3;  
5.     public static final int SECOND_VALUE = 5;  
6.     /*use 'Set' to reject duplicate string.Maybe we should do this at the very beginning(create the string),but how? 
7. I google it,and I find this: 
8. 1.let data = { 1, 2, 6, 3, 4, 5 }; 
9. 2.get all the permutation of 'data',but only store the strings which match "str.matches("^.*6.*2.*$")" (or str.matches("^.*2.*6.*$")) 
10. 3.str.replace('6','2') 
11.         */  
12.     private Set<String> resultSet=new HashSet<String>();  
13.       
14.     public static void main(String[] args) {  
15.         Perm p = new Perm();  
16.         int[] data = { 1, 2, 2, 3, 4, 5 };  
17.         p.perm(data, 0, data.length - 1);  
18.         Set<String> set=p.getResultSet();  
19.         for(String str :set){  
20.             System.out.println(str);  
21.         }  
22.         System.out.println(set.size());  
23.           
24.     }  
25.   
26.     //find all possible combination  
27.     public void perm(int[] data, int begin, int end) {  
28.         if (data == null || data.length == 0) {  
29.             return;  
30.         }  
31.         if (begin == end) {  
32.             boolean ok = check(data);//exclude the 'bad' string  
33.             if (ok) {  
34.                 String str=stringOf(data);  
35.                 resultSet.add(str);  
36.             }  
37.         }  
38.         for (int i = begin; i <= end; i++) {  
39.             swap(data, begin, i);  
40.             perm(data, begin + 1, end);  
41.             swap(data, begin, i);  
42.         }  
43.     }  
44.   
45.     //exclude the 'bad' string--"4"不能在第三位，"3"与"5"不能相连  
46.        //we can also use regular expression:(!str.matches("^..4.*$")&&!str.matches("^.*((35)|(53)).*$")&&str.matches("^.*2.*6.*$"))  
47.     public boolean check(int[] data) {  
48.         if (data == null || data.length == 0) {  
49.             return false;  
50.         }  
51.         for (int i = 0, len = data.length; i < len - 1; i++) {  
52.             if (data[i] == FIRST_VALUE && data[i + 1] == SECOND_VALUE  
53.                     || data[i + 1] == FIRST_VALUE && data[i] == SECOND_VALUE) {  
54.                 return false;  
55.             }  
56.             if (i + 1 == BAD_INDEX && data[i] == BAD_VALUE) {  
57.                 return false;  
58.             }  
59.         }  
60.         return true;  
61.     }  
62.   
63.     //int[] data = { 1, 2, 2, 3, 4, 5 }-->"122345"  
64.     public String stringOf(int[] x){  
65.         StringBuilder sb=new StringBuilder();  
66.         for(int i=0,len=x.length;i<len;i++){  
67.             sb.append(x[i]);  
68.         }  
69.         return sb.toString();  
70.     }  
71.       
72.     public void swap(int[] x, int i, int j) {  
73.         int tmp = x[i];  
74.         x[i] = x[j];  
75.         x[j] = tmp;  
76.     }  
77.       
78.     public Set<String> getResultSet(){  
79.         return resultSet;  
80.     }  
81. }  

Read full article from 两种方法-用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412325等.要求："4"不能在第三位 - 代码物语-Let code talk - ITeye技术网站