A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 肖德茂 中级黑马   /  2014-6-24 15:54  /  2262 人查看  /  16 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

今天碰到一个问题:排列问题,想了很久没思路,网上只找到组合的,没找到排列的,求解答!问题如下:
有3个数字:1  2  3 ,编写程序,打印出以上3个数字任意多个组成的任意排列。打印出来的结果应当如下:
1  2  3
12  13  23  21  31  32
123  132  213  231  312  321
小弟实在没有什么思路,求思路,最好能附上代码,感激不尽!

16 个回复

倒序浏览
对于这道题我只会一路for。。这样毫无扩展性的代码。。
回复 使用道具 举报
楼主请看
  1. package cm.heima;

  2. public class Demo {
  3.         // -----中间方法
  4.         public static String[] mid(String[] str, String[] middle) {

  5.                 // 原来已经复制过了,现在要定义剩下的数组 ,以便接下来复制
  6.                 String[] end = new String[(middle.length * (str.length - middle[0]
  7.                                 .length()))];

  8.                 // 定义end指针pp
  9.                 int pp = 0;

  10.                 // 双重for 循环 赋值
  11.                 for (int i = 0; i < middle.length; i++) {

  12.                         for (int ii = 0; ii < str.length; ii++) {

  13.                                 // 比较第一个数组的元素 是否在第二个中找到。
  14.                                 if (middle[i].indexOf(str[ii]) < 0) {

  15.                                         // 赋值操作 指针自加
  16.                                         end[pp++] = middle[i] + str[ii];
  17.                                 }
  18.                         }
  19.                 }
  20.                 return end;
  21.         }

  22.         // -------------主方法
  23.         public static String[] turn(String[] str) {
  24.                 // 参数为要打印的字符串个数
  25.                 String[] end = new String[count(str.length)];

  26.                 // 定义end 下标指针 从0开始 复制
  27.                 int pp = 0;

  28.                 System.arraycopy(str, 0, end, pp, str.length);

  29.                 // 复制过后,指针 改变
  30.                 pp += str.length;

  31.                 String[] middle = str;

  32.                 for (int i = 0; i < str.length - 1; i++) {

  33.                         middle = mid(str, middle);

  34.                         System.arraycopy(middle, 0, end, pp, middle.length);

  35.                         pp += middle.length;
  36.                 }
  37.                 return end;
  38.         }

  39.         /**
  40.          * 计数返回数组维数
  41.          */
  42.         public static int count(int length) {
  43.                 if (length > 1)

  44.                         // 递归调用
  45.                         return length + length * count(length - 1);

  46.                 else
  47.                         return 1;
  48.         }

  49.         /**
  50.          * 打印数组
  51.          *
  52.          * @param str
  53.          */
  54.         public static void show(String[] str) // ------------打印数组
  55.         {
  56.                 for (String i : str) {

  57.                         System.out.print(i + "\t");
  58.                 }

  59.                 System.out.println();
  60.         }

  61.         public static void main(String[] args) {

  62.                 String[] str1 = { "1", "2", "3" };

  63.                 // System.out.println("count=" + Test8.count(str1.length));
  64.                 // 转换
  65.                 show(turn(str1));
  66.         }
  67. }
复制代码

点评

亲自运行了一下,发现果然强大,虽然格式没弄,但是结果是出来了,具备通用性。  发表于 2014-6-26 00:41
没怎么看,你这个代码可以实现4个元素的排序吗?  发表于 2014-6-26 00:36
回复 使用道具 举报

好的,回头慢慢看~~~强大~~~~~~~~~~~~
回复 使用道具 举报
黑马有一个基础测试题  和这个题目类似

楼主你看看,参考一下。


/**
* 第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);
                }
               
        }
}
回复 使用道具 举报
简单的实现方法可以用递归思想,还需要代码的话回复一下
回复 使用道具 举报
学习了!
回复 使用道具 举报
本帖最后由 fantacyleo 于 2014-6-26 00:39 编辑

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

  2.     static int[] used; // 记录某个下标是否已经在排列中
  3.     static char[] chars; // 用户输入的字符串拆成单个字符,保存于此
  4.     static char[] result; // 保存一个排列结果


  5.     public static void main(String[] args) {
  6.         if(args.length != 1) // 要求在命令行输入一个字符串
  7.             System.out.println("Usage: java Permute abc");
  8.         else
  9.             calPermutation(args[0]);
  10.     }

  11.     static void calPermutation(String s) {
  12.         chars = s.toCharArray();
  13.         int i;

  14.         for(i = 1; i <= chars.length; i++) {
  15.             used = new int[chars.length];
  16.             result = new char[i];
  17.             deepFirstSearch(i, 0);
  18.             System.out.println();
  19.         }
  20.     }

  21.     static void deepFirstSearch(int len, int index) {
  22.         if(len == index) // 达到排列长度要求,打印一次排列的结果
  23.         {
  24.             int i;
  25.             for(i = 0; i < result.length; i++)
  26.                 System.out.print(result[i]);
  27.             System.out.print(" ");
  28.         }
  29.         else
  30.         {
  31.             int i;
  32.             for(i = 0; i < chars.length; i++) // chars数组下标
  33.             {
  34.                 if(used == 0) // 如果该下标尚未使用过
  35.                 {
  36.                     used[i] = 1; // 标记为已使用
  37.                     result[index] = chars[i]; // 将字符放入结果数组
  38.                     deepFirstSearch(len, index + 1); // 递归完成余下的排列
  39.                     used[i] = 0; // 回溯
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
复制代码



回复 使用道具 举报
上面的代码可以接收任何长度的字符串(当然太长了会很慢: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放入结果数组,此时排列长度达到要求,输出此排列。
回复 使用道具 举报
fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法,效率不高,但正确性可以保证,希望对楼主有帮助。

高手啊!
回复 使用道具 举报
fantacyleo 发表于 2014-6-26 00:29
写了一个深度优先搜索的算法,效率不高,但正确性可以保证,希望对楼主有帮助。

好的~~~~谢谢谢谢!!!!
回复 使用道具 举报
_qishiwobusha_ 发表于 2014-6-25 16:55
黑马有一个基础测试题  和这个题目类似

楼主你看看,参考一下。

很好,谢谢谢谢!!!!!
回复 使用道具 举报
刚好也遇到这题,受教了
回复 使用道具 举报
晕了.........
回复 使用道具 举报
找了一下网上的代码,感觉这个代码算是稍微简单明了的了。。。但还是看的云里雾里的, 分享一下给有同疑问的们:
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();
    }
}
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马