题目：6个数：1,2,2,3,4,5，如何取出所有排列。
1、
这道题其实想法非常简单，就是从123445到544321的数字输出出来，这其中需要去掉一些无效的数字，例如6,7,8,9,0. 其实这道题还可以不断向上添加限制条件，例如要求4不能在第三个位置，3和5不能连在一起，这些条件可以和6,7,8,9,0是非法数字这个条件看做并列的条件，只要把存在这样的数字设置为无效即可。
反思：这道题的想法非常巧妙和简单，一开始碰到这题，以为一定是用排列组合的方法来做了，我还试着用插空法来解决这个问题，后来发现实在太复杂，后来网上看到这个想法，佩服，看来还要低头多学习啊！
代码如下：
package job; public class Permutation2 { private static String[] forbidenNumber = new String[] { "0", "6", "7", "8", "9" }; private static String[] mustExistNumber = new String[] { "1", "2", "2", "3", "4", "5" }; private static boolean isValidNumber(String str) { // 检查是否有非法数字，有返回false，否则继续 for (String number : forbidenNumber) { if (str.indexOf(number) >= 0) { return false; } } // 检查是否存在要的数字，如果不存在返回false，否则继续 for (String number : mustExistNumber) { int temp = str.indexOf(number); if (temp < 0) { return false; } else if ((str.indexOf(number, temp + 1) > temp) //就是在找到了一个number的后面再找到这个number，如果这个number不是2，那也返回false && str.charAt(temp) != '2') { return false; } } // 检查4在不在第三位，是返回false if (str.charAt(2) == '4') { return false; } // 检查是否存在35在一起，有返回false if (str.indexOf("35") >= 0 || str.indexOf("53") >= 0) { return false; } return true; } public static void main(String[] args) { // TODO code application logic here for (int i = 122345; i < 543221; i++) { if (isValidNumber(String.valueOf(i))) { System.out.println(i); } } } }
http://blog.sina.com.cn/s/blog_71f4ccf90101jzdb.html
2、
到这里还没完，如果说我们就是想用排列组合的方法来解决怎么办？下面给出一种用递归算法解决的方法。
先把这道题的条件降低，我们先排列1,2,3,4,5这五个数字，仔细体会递归算法的使用
package job; public class Permutation { static int[] bits = new int[] { 1, 2, 3, 4, 5 }; public static void main(String[] args) { sort("", bits); } private static void sort(String prefix, int[] a) { //注意体会递归的优点，怎么想到的呢？ if (a.length == 1) System.out.println(prefix + a[0]); for (int i = 0; i < a.length; i++) sort(prefix + a[i], copy(a, i)); } private static int[] copy(int[] a,int index){ int[] b = new int[a.length-1]; System.arraycopy(a, 0, b, 0, index); System.arraycopy(a, index+1, b, index, a.length-index-1); return b; } }
然后，我们加大条件使得和最初的条件一样：排列1,2,2,3,4,5，然后4在第三位，3和5不相连。
基本思路：
把问题归结为图结构的遍历问题。图遍历思想：实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
显然这个结果集还未达到题目的要求。从以下几个方面考虑：
3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
代码如下：
package job; import java.util.Iterator; import java.util.TreeSet; /** * 问题描述：对1,2,2,3,4,5排列，4不许在第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不能在第三位: 仍旧在结果集中去除满足此条件的结果。 * @author hanson * */ public class Permutation3 { private String[] b = new String[]{"1", "2", "2", "3", "4", "5"}; private int n = b.length; private boolean[] visited = new boolean[n]; private int[][] a = new int[n][n]; private String result = ""; private TreeSet set = new TreeSet(); public static void main(String[] args) { new Permutation3().start(); } private void start() { // Initial the map a[][] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { a[i][j] = 0; } else { a[i][j] = 1; } } } // 3 and 5 can not be the neighbor. a[3][5] = 0; a[5][3] = 0; // Begin to depth search. for (int i = 0; i < n; i++) { this.depthFirstSearch(i); } // Print result treeset. Iterator it = set.iterator(); while (it.hasNext()) { String string = (String) it.next(); // "4" can not be the third position. if (string.indexOf("4") != 2) { System.out.println(string); } } } private void depthFirstSearch(int startIndex) { visited[startIndex] = true; result = result + b[startIndex]; if (result.length() == n) { // Filt the duplicate value. set.add(result); } for(int j = 0; j < n; j++) { if (a[startIndex][j] == 1 && visited[j] == false) { //如果节点j和节点startIndex相连，且节点j没有被访问，就从j开始深度优先遍历 depthFirstSearch(j); } else { continue; } } // restore the result value and visited value after listing a node. result = result.substring(0, result.length() -1); visited[startIndex] = false; } }
递归的方法好难想啊！