用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列
用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连?
?
这道笔试题相当的出名，我也有幸遇到了。确切的说这是一道算法题，像我这种离散，数据结构都半吊子的人实在拿它没撤，回来小发愤了一下，找到了多个不同的实现算法
第一个：
package com.audition;//排序组合算法public class PermutationAlgo { private int count = 0; public void calculate(){ String eleStr = "122345"; depthSearch(eleStr, ""); System.out.println("符合条件的总结果数为:"+count+"条"); } /** * @param eleStr - 待分配字符组成的串 * @param rstStr - 已分配字符组成的串 */ public void depthSearch(String eleStr, String rstStr) { if (eleStr.length() == 0) { count++; System.out.println(rstStr); return; } for (int i = 0; i < eleStr.length(); i++) { String currEle = eleStr.substring(i, i + 1); //取出当前位的值 if (rstStr.length() == 2 && "4".equals(currEle)) continue; //剪掉第三位为4的分支 if (rstStr.endsWith("3") && "5".equals(currEle)) continue; //剪掉"35"相连的分支 if (rstStr.endsWith("5") && "3".equals(currEle)) continue; //剪掉"53"相连的分支 if (eleStr.substring(0, i).indexOf(currEle) != -1) continue; //剪掉同一位上字符重复的分支(此题即剪掉重复的2) depthSearch(eleStr.substring(0, i) + eleStr.substring(i + 1), rstStr + currEle); //用剩余的合法串继续递归 } } public static void main(String[] args) { new PermutationAlgo().calculate(); }}?第二个
package com.audition;public class PermutationAlgo2 {private static int count = 0; public static void main(String[] args) { // 本题的思路是先用 1,3,4,5 进行全排列 // 后边再将另外两个 2 往里插入，并判断是否符合要求 int[] arr = { 1, 3, 4, 5 }; printCom(arr, 0); System.out.printf("符合要求的排列共有 %d 种", count); } public static void printCom(int[] arr, int index) { if (index == arr.length - 1) { insertTwo(arr, 0); return; } printCom(arr, index + 1); for (int i = index + 1; i < arr.length; i++) { arr[index] ^= arr[i]; arr[i] ^= arr[index]; arr[index] ^= arr[i]; printCom(arr, index + 1); arr[index] ^= arr[i]; arr[i] ^= arr[index]; arr[index] ^= arr[i]; } } // 将 2 在符合要求的情况下插入数组 private static void insertTwo(int[] arr, int index) { if (index == arr.length + 1) return; for (int i = index + 1; i < arr.length + 2; i++) { int[] tar = new int[arr.length + 2]; tar[i] = 2; tar[index] = 2; innerInsert(arr, tar); } insertTwo(arr, index + 1); } private static void innerInsert(int[] arr, int[] tar) { int index = 0; int indexArr = 0; while (index < tar.length) { if (tar[index] == 0) { if ((index > 0 && tar[index - 1] + arr[indexArr] == 8) || (index == 2 && arr[indexArr] == 4)) return; tar[index] = arr[indexArr++]; } index++; } count++; System.out.printf("[%d]", count); for (int i = 0; i < tar.length; i++) { System.out.print(tar[i] + " "); } if(count % 5 == 0){ System.out.println(); } }}?第三个
package com.audition;/** * 用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5" * 不能相连。 * * * @author Administrator * */public class PermutationAlgo3 {private int[] numbers = new int[] { 1, 2, 2, 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) {PermutationAlgo3 algo3 = new PermutationAlgo3();algo3.list("", "");System.out.println("总数：" + algo3.n);}}?运行结果都是198个
?
?
(6!-5!-5*(4!)+3*(3!)*2)/22 楼 xiangxuehai_jiaer 2011-10-15 idea: