一道有条件的数字排列面试题

原题如下：用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。

一.全排列解法：
package com.heyang.p122345;

import java.util.HashSet;
import java.util.Set;


public class Permutation{
    // 用于序号
    private static int  index=1;
   
    // 用于清除重复的数，因为有两个2的影响
    private static Set<String> set=new HashSet<String>();
   
    public static void main(String[] args){
        Integer[] arr02={1,2,2,3,4,5};
        //Integer[] arr02={1,2,2};
        permutation(arr02,0,arr02.length);
    }
   
   
    public static void permutation(Integer[] arr,int start,int end){
        if(start<end+1){
            permutation(arr,start+1,end);
           
            for(int i=start+1;i<end;i++){
                Integer temp;
               
                temp=arr[start];
                arr[start]=arr[i];
                arr[i]=temp;
               
                permutation(arr,start+1,end);
               
                temp=arr[i];
                arr[i]=arr[start];
                arr[start]=temp;
            }
        }
        else{
            print(arr);
        }
    }

   
    private static void print(Integer[] arr){
        // "4"不能在第三位
        if(arr[2]==4){
            return;
        }
       
        StringBuilder sb=new StringBuilder();
       
        for(int i=0;i<arr.length;i++){
            sb.append(arr[i]);
        }
       
        String word=sb.toString();
       
        // "3"与"5"不能相连
        if(word.contains("35") || word.contains("53")){
            return;
        }
       
        // 打印
        if(set.contains(word)==false){
            System.out.println((index++)+" "+word);
            set.add(word);
        }
    }
}
输出：
1 122345
2 122543
3 123245
4 123254
5 123425
6 123452
7 125432
8 125423
9 125243
10 125234
11 132245
12 132254
13 132425
14 132452
15 132542
16 132524
17 142325
18 142523
19 143225
20 143252
21 145232
22 145223
23 152342
24 152324
25 152432
26 152423
27 152243
28 152234
29 212345
30 212543
31 213245
32 213254
33 213425
34 213452
35 215432
36 215423
37 215243
38 215234
39 221345
40 221543
41 223145
42 223154
43 223415
44 223451
45 225431
46 225413
47 225143
48 225134
49 232145
50 232154
51 232415
52 232451
53 232541
54 232514
55 231245
56 231254
57 231425
58 231452
59 231542
60 231524
61 242315
62 242513
63 243215
64 243251
65 243125
66 243152
67 241325
68 241523
69 245132
70 245123
71 245213
72 245231
73 252341
74 252314
75 252431
76 252413
77 252143
78 252134
79 251342
80 251324
81 251432
82 251423
83 251243
84 251234
85 322145
86 322154
87 322415
88 322451
89 322541
90 322514
91 321245
92 321254
93 321425
94 321452
95 321542
96 321524
97 325142
98 325124
99 325412
100 325421
101 325241
102 325214
103 312245
104 312254
105 312425
106 312452
107 312542
108 312524
109 315242
110 315224
111 315422
112 342125
113 342152
114 342215
115 342251
116 342521
117 342512
118 341225
119 341252
120 341522
121 345122
122 345212
123 345221
124 422315
125 422513
126 423215
127 423251
128 423125
129 423152
130 421325
131 421523
132 425132
133 425123
134 425213
135 425231
136 432215
137 432251
138 432125
139 432152
140 432512
141 432521
142 431225
143 431252
144 431522
145 412325
146 412523
147 413225
148 413252
149 415232
150 415223
151 452312
152 452321
153 452132
154 452123
155 452213
156 452231
157 451322
158 451232
159 451223
160 522341
161 522314
162 522431
163 522413
164 522143
165 522134
166 523241
167 523214
168 523421
169 523412
170 523142
171 523124
172 521342
173 521324
174 521432
175 521423
176 521243
177 521234
178 542321
179 542312
180 542231
181 542213
182 542123
183 542132
184 543221
185 543212
186 543122
187 541322
188 541232
189 541223
190 512342
191 512324
192 512432
193 512423
194 512243
195 512234
196 513242
197 513224
198 513422


二.循环解法：
package com.heyang.p122345;



public class Loop{
    // 用于序号
    private static int  index=1;
   
    public static void main(String[] args){
        // 这个数组用来放置百万，十万，万，千，百，十，个位数字
        int[] arr=new int[6];
       
        // 这个用来存储数字转化成的字符串
        String word;
       
        int j;
        // i在能排列出来的最大值和最小值之间循环
        for(int i=122345;i<=543221;i++){
            // 得到百万，十万，万，千，百，十，个位数字
            for(j=0;j<arr.length;j++){
                arr[j]=(i/(power(6-j))) % 10;
            }
           
            // 0，6-9都被排除
            if(hasExtraNumber(arr)==true){
                continue;
            }
           
            // "4"不能在第三位
            if(arr[2]==4){
                continue;
            }
           
            word=String.valueOf(i);
           
            // "3"与"5"不能相连
            if(word.contains("35") || word.contains("53")){
                continue;
            }
           
            // 只有2可以连两次
            if(judge(arr)==false){
                continue;
            }
           
            // 打印
            System.out.println((index++)+" "+word);
            //System.out.println(i+"  "+arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+arr[5]);
        }
    }
   
    private static boolean judge(int[] arr){
        int n1=0,n2=0,n3=0,n4=0,n5=0;
       
        for(int j=0;j<arr.length;j++){
            if(arr[j]==1){
                n1++;
            }
           
            if(arr[j]==2){
                n2++;
            }
           
            if(arr[j]==3){
                n3++;
            }
           
            if(arr[j]==4){
                n4++;
            }
           
            if(arr[j]==5){
                n5++;
            }
        }
       
        return n1==1 && n2==2 && n3==1 && n4==1 && n5==1;
    }
   
   
    private static boolean hasExtraNumber(int[] arr){
        for(int j=0;j<arr.length;j++){
            if(arr[j]<1 || arr[j]>5){
                return true;
            }
        }
       
        return false;
    }
   
   
    private static int power(int n){
        int retval=1;
       
        for(int i=0;i<n-1;i++){
            retval*=10;
        }
       
        return retval;
    }
}
输出：
1 122345
2 122543
3 123245
4 123254
5 123425
6 123452
7 125234
8 125243
9 125423
10 125432
11 132245
12 132254
13 132425
14 132452
15 132524
16 132542
17 142325
18 142523
19 143225
20 143252
21 145223
22 145232
23 152234
24 152243
25 152324
26 152342
27 152423
28 152432
29 212345
30 212543
31 213245
32 213254
33 213425
34 213452
35 215234
36 215243
37 215423
38 215432
39 221345
40 221543
41 223145
42 223154
43 223415
44 223451
45 225134
46 225143
47 225413
48 225431
49 231245
50 231254
51 231425
52 231452
53 231524
54 231542
55 232145
56 232154
57 232415
58 232451
59 232514
60 232541
61 241325
62 241523
63 242315
64 242513
65 243125
66 243152
67 243215
68 243251
69 245123
70 245132
71 245213
72 245231
73 251234
74 251243
75 251324
76 251342
77 251423
78 251432
79 252134
80 252143
81 252314
82 252341
83 252413
84 252431
85 312245
86 312254
87 312425
88 312452
89 312524
90 312542
91 315224
92 315242
93 315422
94 321245
95 321254
96 321425
97 321452
98 321524
99 321542
100 322145
101 322154
102 322415
103 322451
104 322514
105 322541
106 325124
107 325142
108 325214
109 325241
110 325412
111 325421
112 341225
113 341252
114 341522
115 342125
116 342152
117 342215
118 342251
119 342512
120 342521
121 345122
122 345212
123 345221
124 412325
125 412523
126 413225
127 413252
128 415223
129 415232
130 421325
131 421523
132 422315
133 422513
134 423125
135 423152
136 423215
137 423251
138 425123
139 425132
140 425213
141 425231
142 431225
143 431252
144 431522
145 432125
146 432152
147 432215
148 432251
149 432512
150 432521
151 451223
152 451232
153 451322
154 452123
155 452132
156 452213
157 452231
158 452312
159 452321
160 512234
161 512243
162 512324
163 512342
164 512423
165 512432
166 513224
167 513242
168 513422
169 521234
170 521243
171 521324
172 521342
173 521423
174 521432
175 522134
176 522143
177 522314
178 522341
179 522413
180 522431
181 523124
182 523142
183 523214
184 523241
185 523412
186 523421
187 541223
188 541232
189 541322
190 542123
191 542132
192 542213
193 542231
194 542312
195 542321
196 543122
197 543212
198 543221