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

from:http://www.blogjava.net/chen45257211/articles/354718.html

1、2、2、3、4、5这六个数字，写一个main函数，打印出所有不同的排列，

如：512234、412345等，要求："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不能在第三位: 仍旧在结果集中去除满足此条件的结果。 

采用二维数组定义图结构，最后的代码是： 

Java代码  

1. import java.util.Iterator;  
2. import java.util.TreeSet;  
3.   
4. public class TestQuestion {  
5.   
6. private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};  
7. private int n = b.length;  
8. private boolean[] visited = new boolean[n];  
9. private int[][] a = new int[n][n];  
10. private String result = "";  
11. private TreeSet set = new TreeSet();  
12.   
13. public static void main(String[] args) {  
14. new TestQuestion().start();  
15. }  
16.   
17. private void start() {  
18.   
19. // Initial the map a[][]  
20. for (int i = 0; i < n; i++) {  
21. for (int j = 0; j < n; j++) {  
22. if (i == j) {  
23. a[i][j] = 0;  
24. } else {  
25.     a[i][j] = 1;  
26. }  
27. }  
28. }  
29.   
30. // 3 and 5 can not be the neighbor.  
31. a[3][5] = 0;  
32. a[5][3] = 0;  
33.   
34. // Begin to depth　search.  
35. for (int i = 0; i < n; i++) {  
36.     this.depthFirstSearch(i);  
37. }  
38.   
39. // Print result treeset.  
40. Iterator it = set.iterator();  
41. while (it.hasNext()) {  
42. String string = (String) it.next();  
43. // "4" can not be the third position.  
44. if (string.indexOf("4") != 2) {  
45. System.out.println(string);  
46. }  
47. }  
48. }  
49.   
50. private void depthFirstSearch(int startIndex) {  
51. visited[startIndex] = true;  
52. result = result + b[startIndex];  
53. if (result.length() == n) {  
54. // Filt the duplicate value.  
55. set.add(result);  
56. }  
57. for(int j = 0; j < n; j++) {  
58. if (a[startIndex][j] == 1 && visited[j] == false) {  
59. depthFirstSearch(j);  
60. } else {  
61. continue;  
62. }  
63. }  
64.   
65. // restore the result value and visited value after listing a node.  
66.     result = result.substring(0, result.length() -1);  
67.     visited[startIndex] = false;  
68. }  
69. }