黑马程序员技术交流社区

标题: 编程列出一个字符串的全字符组合情况串中 递归问题 [打印本页]
作者: youcyou    时间: 2014-5-10 13:51
标题: 编程列出一个字符串的全字符组合情况串中 递归问题
本帖最后由 youcyou 于 2014-5-14 17:17 编辑

编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符
例如：
原始字符串是"abc"，打印得到下列所有组合情况
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
还是这个老问题，下面是我写的代码，求大神帮忙看一下
  1. import java.util.ArrayList;


  4. public class Test5 {

  6.         
  7.         public static void main(String args[])
  8.         {
  9.                 String s="abc";
  10.                 combinations(s);
  11.         }

  13.         private static void combinations(String s) {
  14.                 combinations("",s);
  15.                
  16.         }

  18.         private static void combinations(String st,String s) {
  19.                 ArrayList<Character> al =new ArrayList<Character>();
  20.                 char[] ch = s.toCharArray();
  21.                 for(char c:ch)
  22.                 {
  23.                         al.add(c);
  24.                 }
  25.                 getString(al,st);
  26.         }
  27.         private static void getString(ArrayList<Character> al,String st)
  28.         {
  29.                 for(int index=0;index<al.size();index++)
  30.                 {               
  31.                         String str=st+al.get(index);
  32.                         System.out.println(str);
  33.                
  34.                         al.remove(index);
  35.                         
  36.                         getString(al,str);
  37.                 }
  38.         }
  39. }
复制代码
作者: pandapan    时间: 2014-5-14 13:34
这位同学，代码的31行到36行出现了问题，可能是你对引用类型的理解存在一点偏差，其实从getString(ArrayList<Character> al,String st)开始，你操作的都是同一个al，不知道这样说你是否能够理解，因为你每次都是在将这个al的引用传递给下一次递归。也就是说从头开始都是在删除al集合中的内容，所以第一次完整的递归，即st=“”->st="a"->st="ab"->st="abc"之后，al集合中已经没有内容了，所以就结束了。
这是我修正之后的代码，就是在这里将al复制了一份，操作复制的即可。
  1.         private static void getString(ArrayList<Character> al,String prefix)
  2.         {
  3.                 for(int index=0;index<al.size();index++)
  4.                 {            
  5.                         ArrayList<Character> alCopy = new ArrayList<Character>();
  6.                         alCopy.addAll(al);
  7.                         String str=prefix+alCopy.get(index);
  8.                         System.out.println(str);
  9.                         alCopy.remove(index);
  10.                         getString(alCopy,str);
  11.                 }
  12.         }
复制代码


，另外，我自己也写了一个，不过没有使用ArrayList，使用的是StringBuilder.咱们的思想应该是差不多的，我也是将字符串进行分成两部分，一个是前缀，另外一个是剩下的串。

  2. public class Test {
  3.         private static int count=0;
  4.         public static void main(String[] args) {
  5.                 // TODO Auto-generated method stub
  6.                 getDiffCombination("","abc");
  7.                 System.out.println(count);
  8.         }
  9.        
  10.         /**
  11.          * 整体的思维方式是，将串分成两部分，一部分为前缀，即 不需要修改的，另外一部分是剩下的串，
  12.          * 如果剩下的串的长度为1，那么构成规则便只有一种，就是前缀+剩下的长度为1的串
  13.          * 否则，便可以将剩下的串进行再次分割，将剩下的串的每一位拼接到前缀，递归寻找结果
  14.          * @param prefix 字符串的构成前缀
  15.          * @param strLeft 剩下的字符串
  16.          */
  17.         private static void getDiffCombination(String prefix,String strLeft){
  18.                 if(strLeft.length()==1){
  19.                         System.out.println(prefix+strLeft);
  20.                         count++;
  21.                         return;
  22.                 }
  23.                
  24.                 for(int i=0;i<strLeft.length();i++){
  25.                         StringBuilder sb = new StringBuilder(strLeft);
  26.                         String str = prefix+strLeft.substring(i, i+1);
  27.                         System.out.println(str);
  28.                         count++;
  29.                         getDiffCombination(str,sb.deleteCharAt(i).toString());
  30.                 }
  31.         }       
  32. }
复制代码

希望能够帮到你
作者: pandapan    时间: 2014-5-14 13:38
另外，这位同学，都能操作到这里了，咱们也就可以操作更进一步的问题了，编程列出一个字符串的全字符组合情况，原始字符串中可能存在重复的字符，这里的操作，考虑使用ArrayList存储每一个的遍历结果，如果这个构成的串已经在ArrayList中存在，那么便直接跳过即可
作者: youcyou    时间: 2014-5-14 17:17
pandapan 发表于 2014-5-14 13:38
另外，这位同学，都能操作到这里了，咱们也就可以操作更进一步的问题了，编程列出一个字符串的全字符组合情 ...

明白了  谢谢指点
作者: 大漠孤烟    时间: 2014-5-14 21:14
学习啦，这个我还真不会，没试过、、、、
作者: Dark_Horse    时间: 2014-5-21 15:48
学习学习....
作者: 黄宽    时间: 2014-10-18 13:15
数组的组合遍历还没好好学，还要下点功夫才行:)
作者: franksight    时间: 2015-2-15 11:58
很好很好。。
作者: 白羊Mon    时间: 2015-3-14 22:16
有用，谢谢
作者: wk843620202    时间: 2015-4-28 00:48
很好啊！
作者: 知识改变人生    时间: 2015-5-8 21:36
都是高手。
作者: shero    时间: 2015-7-28 10:27
很好，有用。
作者: 王劲松    时间: 2015-7-28 21:52
很好，很强大
作者: 15225159271    时间: 2015-7-29 10:48
pandapan 发表于 2014-5-14 13:34
这位同学，代码的31行到36行出现了问题，可能是你对引用类型的理解存在一点偏差，其实从getString(ArrayLis ...

学习了，我在思考联系一下
作者: 千山万水    时间: 2015-8-3 20:48
嗯   。。。。。。。。。。。。。。。。
作者: 巧克黑力    时间: 2015-8-7 10:09
这是基础题呀    感觉到有点难啊
作者: wwfangfang    时间: 2015-8-20 18:36
牛人！！！
作者: hushun135    时间: 2015-9-13 17:18
高手  我还得继续努力学习啊！
作者: 643997890    时间: 2015-9-13 21:45
6666666
666
作者: wangyoucao    时间: 2015-11-28 22:20
这个题确实，看着简单，其实还是有点难度的，今天刚做完，嘿嘿。来学习下不同的思想。。
作者: olivor    时间: 2016-1-3 22:25
还得多看看几遍
作者: 愿随风丶飘雪    时间: 2016-1-16 22:20
都是大神啊,领教了
作者: 愿随风丶飘雪    时间: 2016-1-17 15:06
问一下不使用递归可以吗



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