问题描述：针对1、2、2、3、4、5这6个数字，写一个函数，打印出所有不同的排列，例如512234、215432等，要求“4”不能在第三位，“3”与“5”不能相连。
问题分析：打印数组的排列组合方式最简单的方法就是递归，但是本题中：①数字中存在重复数字②明确规定某些位的特性。采用常规的求解方法不能完全适用。
算法思想：（图思想）把6个数字的组合问题变为图的遍历问题。首先，用1、2、2、3、4、5这6个数字作为6个结点，构造一个无向连通图，除了“3”和“5”不连通。其次，分别从这6个结点出发对图做深度优先遍历。最后，为了去掉重复结果集，将遍历结果存入set集合。最后遍历set集合。
package com.haobi; import java.util.HashSet; import java.util.Iterator; import java.util.Set; /* * 如何按要求打印数组的排列情况 */ public class Test1 { //将元素存入数组 private int[] numbers = new int[] {1,2,2,3,4,5}; //获取数组长度 private int n = numbers.length; //标记图中的结点是否被遍历过 private boolean[] visited = new boolean[n]; //图的二维数组表示 private int[][] graph = new int[n][n]; //数字的组合 private String combination = ""; //用Set集合存储数字组合(过滤重复组合) private Set<String> getAllCombinations(){ //构造图 buildGraph(); //用来存放所有组合 Set<String> set = new HashSet<String>(); //分别从不同的结点出发深度遍历图 for(int i=0;i<n;i++) { this.depthFirstSearch(i, set); } return set; } /** * 构造图 */ private void buildGraph() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==j) { graph[i][j]=0; }else { graph[i][j]=1; } } } //确保在遍历的时候3与5是不可达的 graph[3][5]=0; graph[5][3]=0; } /** * 对图从结点start位置开始进行深度优先搜索遍历 * @param start * @param set */ private void depthFirstSearch(int start, Set<String> set) { //遍历过的结点标记为true visited[start] = true; //数字组合 combination = combination + numbers[start]; //如果组合完毕,组合的长度等于n(也就是数组的长度) if(combination.length() == n) { //根据题目要求，剔除4出现在第三个位置的情况 if(combination.indexOf("4")!=2) { //将符合要求的结果添加进set集合 set.add(combination); } } for(int j=0;j<n;j++) { if(graph[start][j] == 1 && visited[j] == false) { //采用递归(连通图的深度优先搜索遍历是一个递归过程) depthFirstSearch(j, set); } } combination = combination.substring(0, combination.length()-1); //一趟标记完之后，将遍历过的路径设还原为false visited[start] = false; } public static void main(String[] args) { Test1 t = new Test1(); Set<String> set = t.getAllCombinations(); Iterator<String> it = set.iterator(); while(it.hasNext()) { String str = (String)it.next(); System.out.println(str); } } }程序输出结果如下：
322145 512234 225134 231245 415223 325421 512342 322154 243125 542312 541223 232451 123452 523142 251423 422315 243251 542321 541232 152342 415232 325412 345122 243215 513224 412523 221345 522143 122345 342521 152234 451322 215234 512243 432125 132524 541322 312452 225143 523241 123425 523124 142325 231254 432251 152243 342512 321254 345221 132254 431225 513242 215243 245213 521423 312542 521432 542132 543221 321245 242513 345212 125432 123254 425231 223415 312425 252314 123245 125423 251342 252431 422513 152423 245231 542123 543212 341522 413252 432215 145232 425123 251432 145223 223451 542231 152432 431252 212543 241523 322451 542213 232154 315242 425132 421325 312524 251324 252413 142523 152324 232145 243152 322541 321452 432512 132452 342152 522314 125243 423125 252341 523412 143225 521234 325142 322415 231524 242315 452231 125234 423251 315224 523421 521243 213425 342251 521324 522413 143252 251234 225431 245123 342125 543122 325241 413225 322514 231542 321425 212345 325124 231425 232514 321542 132245 213452 241325 452132 432521 425213 225413 423152 421523 521342 522431 251243 245132 452123 512432 252143 523214 223154 321524 452312 451223 232415 132542 132425 341252 512423 315422 223145 522134 432152 342215 325214 215423 431522 213245 513422 412325 221543 312245 522341 423215 122543 452213 215432 213254 512324 312254 252134 231452 232541 451232 341225 452321
