本文共 4101 字，大约阅读时间需要 13 分钟。
原题如下：用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。 解题思路： 很明显，这是一个递归算法。我们可以排列将这6个数按从小到大的顺序排一下，如果是1,2,3,4,5,6，那么会有1*2*3*4*5*6= 6!=720个递增的数。但如果是1,2,2,3,4,5，那么在这720个数中一定会有相同的数对出现（由于在这6个数中只有两个数两同，也就是说，如果有重复的数，那么一定是一对数，如122345会出现两次）。 排列的基本规则是分步进行。也就是说，要排列上面6个数，首先应该选择第一个数，这第一个数可以选择这6个数中的任意一个，如选择1.第二步是选择第二个数，这第二个数不能再选择已经选过的数，如1.因此，它只能从后面5个数中选择。如选择2。以此类推。 我们也可以在程序中模拟这一过程。源程序如下： public class test1 { private int [] numbers = new int [] { 1 , 2 , 3 , 3 , 4 , 5 }; public int n; private String lastResult = "" ; private boolean validate(String s) { if (s.compareTo(lastResult) <= 0 ) return false ; if (s.charAt( 2 ) == ' 4 ' ) return false ; if (s.indexOf( " 35 " ) >= 0 || s.indexOf( " 53 " ) >= 0 ) return false ; return true ; } public void list(String index, String result) { for ( int i = 0 ; i < numbers.length; i ++ ) { if (index.indexOf(i + 48 ) < 0 ) { String s = result + String.valueOf(numbers[i]); if (s.length() == numbers.length) { if (validate(s)) { System.out.println(s); lastResult = s; n ++ ; } break ; } list(index + String.valueOf(i), s); } } } public static void main(String[] args) { test1 t = new test1(); t.list( "" , "" ); System.out.println( " 总数： " + t.n); } } 其中list函数是这个算法的核心函数。index参数表示已经选择过的数，用numbers数组的索引表示。如index="012"，表示numbers的前三个数已经被选择，也表示应该选择第四个数了，而这第四个数应该从后三个数中选择。result参数表示临时的数字组合（这个数字组合最多是5个数字，因为，如果到了6个数字，就表示已经有一个结果产生了）。在默认情况下index和result的值都是""。 在validate中使用了 if (s.compareTo(lastResult) <= 0)进行判断，由于按这种方法进行排列，如果这6个数是递增给出的，那么排列的结果一定是递增的，但上述的6个数其中第2和第3个位置上都是2,因此，如果出现了上一个结果不小于当前结果的情况，一定是有重复了，因此，要将这部分数过滤出去。 使用1, 2, 2, 3, 4, 5的测试结果 122345 122543 123245 123254 123425 123452 125234 125243 125423 125432 132245 132254 132425 132452 132524 132542 142325 142523 143225 143252 145223 145232 152234 152243 152324 152342 152423 152432 212345 212543 213245 213254 213425 213452 215234 215243 215423 215432 221345 221543 223145 223154 223415 223451 225134 225143 225413 225431 231245 231254 231425 231452 231524 231542 232145 232154 232415 232451 232514 232541 241325 241523 242315 242513 243125 243152 243215 243251 245123 245132 245213 245231 251234 251243 251324 251342 251423 251432 252134 252143 252314 252341 252413 252431 312245 312254 312425 312452 312524 312542 315224 315242 315422 321245 321254 321425 321452 321524 321542 322145 322154 322415 322451 322514 322541 325124 325142 325214 325241 325412 325421 341225 341252 341522 342125 342152 342215 342251 342512 342521 345122 345212 345221 412325 412523 413225 413252 415223 415232 421325 421523 422315 422513 423125 423152 423215 423251 425123 425132 425213 425231 431225 431252 431522 432125 432152 432215 432251 432512 432521 451223 451232 451322 452123 452132 452213 452231 452312 452321 512234 512243 512324 512342 512423 512432 513224 513242 513422 521234 521243 521324 521342 521423 521432 522134 522143 522314 522341 522413 522431 523124 523142 523214 523241 523412 523421 541223 541232 541322 542123 542132 542213 542231 542312 542321 543122 543212 543221 总数：198 使用1,2, 3, 3, 4, 5的测试结果 123345 125433 132345 132543 133245 133254 133425 133452 143325 145233 152334 152343 152433 213345 215433 231345 231543 233145 233154 233415 233451 243315 245133 251334 251343 251433 312345 312543 313245 313254 313425 313452 315234 315243 315423 315432 321345 321543 323145 323154 323415 323451 325134 325143 325413 325431 331245 331254 331425 331452 331524 331542 332145 332154 332415 332451 332514 332541 341325 341523 342315 342513 343125 343152 343215 343251 345123 345132 345213 345231 413325 415233 423315 425133 431325 431523 432315 432513 433125 433152 433215 433251 451233 451323 451332 452133 452313 452331 512334 512343 512433 513234 513243 513324 513342 513423 513432 521334 521343 521433 523134 523143 523314 523341 523413 523431 541233 541323 541332 542133 542313 542331 543123 543132 543213 543231 543312 543321 总数：118 使用1, 3, 3, 3, 4, 5的测试结果 133345 313345 315433 331345 331543 333145 333154 333415 333451 343315 345133 433315 451333 513334 513343 513433 541333 543133 543313 543331 总数：20
本文转自 androidguy 51CTO博客，原文链接：http://blog.51cto.com/androidguy/216449，如需转载请自行联系原作者