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

解答的大牛，希望给出思路和给出代码的注释谢谢

自己抢板凳，在线等

谁自己解答此题目，奖励3分技术分

1. static int[] bits = new int[] { 1, 2, 3, 4, 5 };
   
2. /**
   
3. * @参数
   
4. */
   
5. public static void main(String[] args) {
   
6. sort("", bits);
   
7. }
   
8. 
   
9. private static void sort(String prefix, int[] a) {
   
10. if (a.length == 1) {
    
11. System.out.println(prefix + a[0]);
    
12. }
    
13. 
    
14. for (int i = 0; i < a.length; i++) {
    
15. sort(prefix + a[i], copy(a, i));
    
16. }
    
17. }
    
18. 
    
19. private static int[] copy(int[] a,int index){
    
20. int[] b = new int[a.length-1];
    
21. System.arraycopy(a, 0, b, 0, index);
    
22. System.arraycopy(a, index+1, b, index, a.length-index-1);
    
23. return b;
    
24. }
    
25. 
    

复制代码

基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对于每一个结点求这个图形的遍历路径，所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑：
  1. 3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
  2. 不能有重复: 考虑到有两个2，明显会存在重复结果，可以把结果集放在TreeSet中过滤重复结果
  3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构，最后的代码是：

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. // 初始化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和5不能相连
    
31. a[3][5] = 0;
    
32. a[5][3] = 0;
    
33. 
    
34. for (int i = 0; i < n; i++) {
    
35. this.depthFirstSearch(i);
    
36. }
    
37. 
    
38. // 打印结果
    
39. Iterator it = set.iterator();
    
40. while (it.hasNext()) {
    
41. String string = (String) it.next();
    
42. //“4”不能在第三的位置
    
43. if (string.indexOf("4") != 2) {
    
44. System.out.println(string);
    
45. }
    
46. }
    
47. }
    
48. 
    
49. private void depthFirstSearch(int startIndex) {
    
50. visited[startIndex] = true;
    
51. result = result + b[startIndex];
    
52. if (result.length() == n) {
    
53. //过滤重复的值
    
54. set.add(result);
    
55. }
    
56. for(int j = 0; j < n; j++) {
    
57. if (a[startIndex][j] == 1 && visited[j] == false) {
    
58. depthFirstSearch(j);
    
59. } else {
    
60. continue;
    
61. }
    
62. }
    
63. 
    
64. // 恢复
    
65. result = result.substring(0, result.length() -1);
    
66. visited[startIndex] = false;
    
67. }
    
68. }
    

复制代码

我有个想法，就是把随机生成的序列放到一个String类型的ArrayList或者数组中，然后遍历集合或者数组，取出的每个字符串进行正则表达式的判断。

王宝康 发表于 2012-7-20 02:01
我有个想法，就是把随机生成的序列放到一个String类型的ArrayList或者数组中，然后遍历集合或者数组，取出 ...

就凭这一分，我一定要做出来！这是被认同的喜悦，哈哈...

滔哥 发表于 2012-7-20 01:40
基本思路：
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点，把六个结点连接成无向连通图，对 ...

{:3_47:}滔哥V5 霸气测漏啊

王艺霖 发表于 2012-7-20 01:35
最简单的就是
                   用外部变量接
1：首先要考虑他们是怎么组合排列的

{:3_46:}羡慕嫉妒恨，你要谢谢我啊，你因为我得了3分啊！算法V5

这个我的代码！

1. /*
   
2. 问题：        用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，
   
3.                 如：512234、212345等，要求："4"不能在第三位，"3"与"5"不能相连。
   
4. */
   
5. public class Demo
   
6. {
   
7.         public static long count = 0;
   
8.         public static void main(String[] args){
   
9.                 final String number = "122345";                        // 自定义N个数字（可以是N个任意字符）
   
10.                 arrange(number,                                                 // 调用arrange方法递归遍历所有排列
    
11.                                 new char[number.length()],
    
12.                                 new boolean[number.length()],
    
13.                                 0);
    
14.                 System.out.println("符合要求的数据共有："+ count +"个.");
    
15.         }
    
16. 
    
17.         // 方法：递归遍历所有排列
    
18.         // 参数：number        需要排列的字符
    
19.         //                 tmp         临时结果数组
    
20.         //                 used       每个字符的使用标识（标记是否已经使用）
    
21.         //                 n              正在遍历的第n个数据
    
22.         public static void arrange(final String number, char[] tmp, boolean[] used, int n){
    
23.                
    
24.                 // 递归出口：当得到一个与number长度相同的数据
    
25.                 if (n == number.length()){
    
26.                         String result = new String(tmp);                   // 将char数组转换为String
    
27. 
    
28.                         // 判断条件："4"不能在第三位，"3"与"5"不能相连
    
29.                         if (tmp[2] != '4' && !result.contains("35") && !result.contains("53")){
    
30.                                 System.out.println(result);
    
31.                                 ++count;                                                // 统计符合要求的结果
    
32.                         }
    
33.                         return;
    
34.                 }
    
35. 
    
36.                 // 递归排列
    
37.                 for (int i=0; i<number.length(); i++){
    
38.                         // 若当前数据为被使用
    
39.                         if (!used[i]){
    
40.                                 used[i] = true;                                        // 使用当前数据
    
41.                                 tmp[n] = number.charAt(i);                  // 将数据填入临时结果数组中
    
42.                                 arrange(number, tmp, used ,n+1);       // 递归遍历下一位数据
    
43.                                 used[i] = false;                                       // 已经使用完当前数据
    
44.                         }
    
45.                 }
    
46.         }
    
47. }

复制代码