黑马程序员技术交流社区

标题: 一个算法问题，求思路和解答 [打印本页]

---

作者: 肖德茂    时间: 2014-6-24 15:54
标题: 一个算法问题，求思路和解答
今天碰到一个问题：排列问题，想了很久没思路，网上只找到组合的，没找到排列的，求解答！问题如下：
有3个数字：1  2  3 ，编写程序，打印出以上3个数字任意多个组成的任意排列。打印出来的结果应当如下：
1  2  3
12  13  23  21  31  32
123  132  213  231  312  321
小弟实在没有什么思路，求思路，最好能附上代码，感激不尽！

---

作者: Alan_Kwan    时间: 2014-6-24 17:36
对于这道题我只会一路for。。这样毫无扩展性的代码。。

---

作者: 毅心缘    时间: 2014-6-24 18:32
楼主请看

1. package cm.heima;
   
2. 
   
3. public class Demo {
   
4.         // -----中间方法
   
5.         public static String[] mid(String[] str, String[] middle) {
   
6. 
   
7.                 // 原来已经复制过了，现在要定义剩下的数组 ，以便接下来复制
   
8.                 String[] end = new String[(middle.length * (str.length - middle[0]
   
9.                                 .length()))];
   
10. 
    
11.                 // 定义end指针pp
    
12.                 int pp = 0;
    
13. 
    
14.                 // 双重for 循环 赋值
    
15.                 for (int i = 0; i < middle.length; i++) {
    
16. 
    
17.                         for (int ii = 0; ii < str.length; ii++) {
    
18. 
    
19.                                 // 比较第一个数组的元素 是否在第二个中找到。
    
20.                                 if (middle[i].indexOf(str[ii]) < 0) {
    
21. 
    
22.                                         // 赋值操作 指针自加
    
23.                                         end[pp++] = middle[i] + str[ii];
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 return end;
    
28.         }
    
29. 
    
30.         // -------------主方法
    
31.         public static String[] turn(String[] str) {
    
32.                 // 参数为要打印的字符串个数
    
33.                 String[] end = new String[count(str.length)];
    
34. 
    
35.                 // 定义end 下标指针 从0开始 复制
    
36.                 int pp = 0;
    
37. 
    
38.                 System.arraycopy(str, 0, end, pp, str.length);
    
39. 
    
40.                 // 复制过后，指针 改变
    
41.                 pp += str.length;
    
42. 
    
43.                 String[] middle = str;
    
44. 
    
45.                 for (int i = 0; i < str.length - 1; i++) {
    
46. 
    
47.                         middle = mid(str, middle);
    
48. 
    
49.                         System.arraycopy(middle, 0, end, pp, middle.length);
    
50. 
    
51.                         pp += middle.length;
    
52.                 }
    
53.                 return end;
    
54.         }
    
55. 
    
56.         /**
    
57.          * 计数返回数组维数
    
58.          */
    
59.         public static int count(int length) {
    
60.                 if (length > 1)
    
61. 
    
62.                         // 递归调用
    
63.                         return length + length * count(length - 1);
    
64. 
    
65.                 else
    
66.                         return 1;
    
67.         }
    
68. 
    
69.         /**
    
70.          * 打印数组
    
71.          *
    
72.          * @param str
    
73.          */
    
74.         public static void show(String[] str) // ------------打印数组
    
75.         {
    
76.                 for (String i : str) {
    
77. 
    
78.                         System.out.print(i + "\t");
    
79.                 }
    
80. 
    
81.                 System.out.println();
    
82.         }
    
83. 
    
84.         public static void main(String[] args) {
    
85. 
    
86.                 String[] str1 = { "1", "2", "3" };
    
87. 
    
88.                 // System.out.println("count=" + Test8.count(str1.length));
    
89.                 // 转换
    
90.                 show(turn(str1));
    
91.         }
    
92. }
    

复制代码

---

作者: 肖德茂    时间: 2014-6-25 15:54

毅心缘 发表于 2014-6-24 18:32
楼主请看

好的，回头慢慢看~~~强大~~~~~~~~~~~~

---

作者: _qishiwobusha_    时间: 2014-6-25 16:55
黑马有一个基础测试题  和这个题目类似

楼主你看看，参考一下。


/**
* 第7题  编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符。
* 例如：原始字符串是"abc"，打印得到下列所有组合情况：
*"a" "b" "c"
*"ab" "bc" "ca" "ba" "cb" "ac"
*"abc" "acb" "bac" "bca" "cab" "cba"
* @author Administrator
*/
/**
* 思路是 先求字符串的所有组合情况，再把每一种的组合情况的所有排列情况求出
*/
public class Test7 {
       
        public static ArrayList<char[]> list =new ArrayList<char[]>();//保存字符串的所有组合情况
        public static ArrayList<String> list2 = new ArrayList<String>();//保存字符串的全字符组合
        public static void main(String[] args) {
                String str = "abc";
                Stack<Character> s = new Stack<Character>();
                selectChar(str.toCharArray(),0,str.length(),s);
                for(int i = 0;i<list.size();i++){
                        char[] c = list.get(i);
                        permutation(c,0,c.length - 1);
                }
                for(int j = 0;j<list2.size();j++){
                        System.out.println(list2.get(j));
                }
        }
/**
* 获得字符串 str 的全部组合情况
* 例如 "abc"  ---> "abc" "ab"  "a"  "ac"  "bc" "b" "c"
* 并把全部组合情况保存到 ArrayList list中
* @param str
* @param begin
* @param m
* @param select
*/
        public static void selectChar(char[] str,int begin,int m,Stack<Character>select){
                if(m == 0){
                        Object[] Ochars = select.toArray();
                        char []chars = new char[Ochars.length];
                        for(int i = 0;i < Ochars.length;i++){
                                chars[i] = (Character)Ochars[i];
                        }
                        list.add(chars);
                        return;
                }
                select.push(str[begin]);
                selectChar(str,begin + 1,m - 1,select);
                select.pop();
                selectChar(str,begin + 1  ,m - 1,select);
        }
        public static void swap(char[]str,int i,int j){
                char temp = str[i];
                str[i] = str[j];
                str[j] = temp;
        }
        /**
         * 求一个字符串的所有排列情况
         * @param str
         * @param begin
         * @param end
         */
        public static void permutation(char[] str,int begin,int end){
                if(begin == end){
                        list2.add(new String(str));
                        return;
                }
                for(int j=begin;j<=end;j++){
                        swap(str,begin,j);
                        permutation(str,begin + 1,end);
                        swap(str,begin,j);
                }
               
        }
}

---

作者: 火线风    时间: 2014-6-25 21:26
简单的实现方法可以用递归思想，还需要代码的话回复一下

---

作者: caohaikuan    时间: 2014-6-25 22:30
学习了！

---

作者: fantacyleo    时间: 2014-6-26 00:29


写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

1. public class Permute {
   
2. 
   
3.     static int[] used; // 记录某个下标是否已经在排列中
   
4.     static char[] chars; // 用户输入的字符串拆成单个字符，保存于此
   
5.     static char[] result; // 保存一个排列结果
   
6. 
   
7. 
   
8.     public static void main(String[] args) {
   
9.         if(args.length != 1) // 要求在命令行输入一个字符串
   
10.             System.out.println("Usage: java Permute abc");
    
11.         else
    
12.             calPermutation(args[0]);
    
13.     }
    
14. 
    
15.     static void calPermutation(String s) {
    
16.         chars = s.toCharArray();
    
17.         int i;
    
18. 
    
19.         for(i = 1; i <= chars.length; i++) {
    
20.             used = new int[chars.length];
    
21.             result = new char[i];
    
22.             deepFirstSearch(i, 0);
    
23.             System.out.println();
    
24.         }
    
25.     }
    
26. 
    
27.     static void deepFirstSearch(int len, int index) {
    
28.         if(len == index) // 达到排列长度要求，打印一次排列的结果
    
29.         {
    
30.             int i;
    
31.             for(i = 0; i < result.length; i++)
    
32.                 System.out.print(result[i]);
    
33.             System.out.print(" ");
    
34.         }
    
35.         else
    
36.         {
    
37.             int i;
    
38.             for(i = 0; i < chars.length; i++) // chars数组下标
    
39.             {
    
40.                 if(used == 0) // 如果该下标尚未使用过
    
41.                 {
    
42.                     used[i] = 1; // 标记为已使用
    
43.                     result[index] = chars[i]; // 将字符放入结果数组
    
44.                     deepFirstSearch(len, index + 1); // 递归完成余下的排列
    
45.                     used[i] = 0; // 回溯
    
46.                 }
    
47.             }
    
48.         }
    
49.     }
    
50. }

复制代码

---

作者: fantacyleo    时间: 2014-6-26 00:48
上面的代码可以接收任何长度的字符串（当然太长了会很慢:lol ）。以"123"为例，预期结果：
1  2  3
12  13  23  21  31  32
123  132  213  231  312  321

思路是：
1. calPermute方法中的循环每次输出一行的结果
2. 每一行的排列由deepFirstSearch方法算出。例如要输出123，(1)把1放入结果数组，标记为已使用，递归 (2)递归再从1开始，由于1已经使用，就看2，2尚未使用，于是标记并放入结果数组，再次递归 (3) 递归发现1，2均已使用，3未使用，于是将3放入结果数组，此时排列长度达到要求，输出此排列。

---

作者: 零下_1°    时间: 2014-6-26 23:54

fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

高手啊！

---

作者: 肖德茂    时间: 2014-6-27 16:28

fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法，效率不高，但正确性可以保证，希望对楼主有帮助。

好的~~~~谢谢谢谢！！！！

---

作者: 肖德茂    时间: 2014-6-27 16:30

_qishiwobusha_ 发表于 2014-6-25 16:55
黑马有一个基础测试题  和这个题目类似

楼主你看看，参考一下。

很好，谢谢谢谢！！！！！

---

作者: 科篮    时间: 2014-7-1 14:00
刚好也遇到这题，受教了

---

作者: 黄梁梦想享    时间: 2014-7-1 17:13
晕了.........

---

作者: Sakuratossi    时间: 2014-8-27 13:15
找了一下网上的代码，感觉这个代码算是稍微简单明了的了。。。但还是看的云里雾里的， 分享一下给有同疑问的们：
public class Test0718 {
    static char[] chars="abcd".toCharArray();
    public static void main(String[] args) {
        for(int i=0;i<chars.length;i++){
            //取得每一个字符
            List<Integer> list=new ArrayList<Integer>();
            list.add(i);
            play(list);
        }
    }
    //使用递归，每次加上列表中不存在的一个字符
    private static void play(List<Integer> list){
        print(list);
        for(int i=0;i<chars.length;i++){
            if(!list.contains(i)){
                List<Integer> temp=new ArrayList<Integer>(list);
                temp.add(i);
                play(temp);
            }
        }
    }
    //打印列表内容
    private static void print(List<Integer> list){
        for(Integer i:list)
            System.out.print(chars[i]+"");
        System.out.println();
    }
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2