黑马程序员技术交流社区

标题: 编程列出一个字符串的全字符组合情况串中 [打印本页]
作者: 官珺伟    时间: 2014-1-6 14:25
标题: 编程列出一个字符串的全字符组合情况串中
本帖最后由 官珺伟 于 2014-1-7 18:23 编辑

编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符
例如：
原始字符串是"abc"，打印得到下列所有组合情况
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
作者: 午夜b'Boy    时间: 2014-1-6 16:55
这题有难度，用到递归算法，
  1. class TurnStr
  2. {
  3.         public static String[] mid(String[] str,String[] middle)    //-----中间方法
  4.         {
  5.                 String[] end =new String[(middle.length*(str.length-middle[0].length()))];
  6.                 int pp=0;
  7.                
  8.                 for (int i=0;i<middle.length;i++)
  9.                 {
  10.                         for (int ii=0;ii<str.length;ii++)
  11.                         {
  12.                                 if (middle[i].indexOf(str[ii])<0)
  13.                                 {
  14.                                         end[pp++]=middle[i]+str[ii];
  15.                                 }
  16.                         }
  17.                 }
  18.                 return end;
  19.         }
  20.        
  21.         public static String[] turn(String[] str)                                //-------------主方法
  22.         {
  23.                 String[] end=new String[count(str.length)];
  24.                 int pp=0;
  25.                 System.arraycopy(str,0,end,pp,str.length);
  26.                 pp+=str.length;
  27.                 String[] middle =str;
  28.                 for (int i=0;i<str.length-1;i++)
  29.                 {
  30.                         middle=mid(str,middle);
  31.                         System.arraycopy(middle,0,end,pp,middle.length);
  32.                   pp+=middle.length;
  33.                 }
  34.                 return end;
  35.         }
  36.        
  37.         public static int count(int length)                                        //---------------计数返回数组维数
  38.         {
  39.                 if (length>1)
  40.                 return length+length*count(length-1);
  41.                 else
  42.                 return 1;
  43.         }
  44.                                
  45.                
  46.         public static void show(String[] str)                                                //------------打印数组
  47.         {
  48.                 for (String i : str)
  49.                 {
  50.                         System.out.print(i+"\t");
  51.                 }
  52.                 System.out.println();
  53.         }
  54.        
  55.         public static void main(String[] args)
  56.         {
  57.                 //String[] str={"A","B","C"};
  58.                 String[] str1={"A","B","C","D"};
  59.                 //TurnStr.show(TurnStr.turn(str));
  60.                 System.out.println(TurnStr.count(str1.length)+"--------------------------------------");
  61.                 show(turn(str1));
  62.         }
  63. }
复制代码
作者: 小悠久    时间: 2014-1-6 17:41
import java.util.Scanner;
import java.util.TreeSet;

public class Test12 {
        public static void main(String[] args) {
                Scanner s = new Scanner(System.in);
               
                String str = s.next();
                System.out.println(str);
               
                s.close();
                show(str);
               

        }
        /**
         * 打印各种可能
         * @param str        str是给定的字符串
         */
        private static void show(String str) {
                TreeSet<String> set = saveInSet(new StringBuilder(str),0,new StringBuilder(),new TreeSet<String>());
                for (String s : set) {
                        System.out.println(s);
                }
        }
        /**
         * 返回集合，集合包含字符串所有字符的可能组合
         * @param str        给定字符串转换成的StringBuilder对象，主要是为了操作字符方便
         * @param count        计数，对第count进行排列组合
         * @param buff        暂存放某种可能
         * @param set        集合，去除重复元素，例如"aab"以第一个a开头会有aba，以第二个a开头也会有aba
         * @return                返回TreeSet集合
         */
        private static TreeSet<String> saveInSet(StringBuilder str, int count, StringBuilder buff, TreeSet<String> set) {
                for (int i = 0,len = str.length(); i < len; i++) {
                        //获取字符
                        char c = str.charAt(i);
                        //去掉原字符串的某个字符（保证某个字符不被重复利用）
                        str.deleteCharAt(i);
                        //缓存添加该字符
                        buff.append(c);
                        //将该种可能组合存入集合
                        set.add(buff.toString());
                        
                        //str仍包含字符，则递归调用，开始取第二位字符
                        //若还有第三位则继续递归……以此类推
                        if (str.length() != 0) {
                                //count用于记录目前在进行排列组合的第count位
                                count++;
                                //递归
                                saveInSet(str,count,buff,set);
                                //第n位递归结束后，需要继续对n-1位排列，位数-1
                                count--;
                        }
                        
                        //递归结束后，需要继续对n-1位排列，因此清除第n位的记录
                        buff.deleteCharAt(count);
                        //删除的字符插回str
                        str.insert(i, c);
                }
                //返回集合
                return set;
               
        }

}
这有详细的注释，你看下。
作者: 宋大人-专注    时间: 2014-6-1 06:51
好好学习一下
作者: 沉默的爱    时间: 2014-6-5 03:08
这题 真有点难啊！想了好久还是没想出来，为了进黑马，借鉴一下了！
作者: LeaonButcher    时间: 2014-6-25 07:58
这是我的解题思路，大致方向还是迭代。
public class Test6 {
        private String originalStr;                //从输入流中读取的字符串       
       
        /**
         * 获得集合，使用迭代进行
         * @param list
         */
        private void getCollection(String strCollection){
                //当迭代到子字符串和原始字符串相同长度时，迭代结束，返回
                if(strCollection.length() == originalStr.length()){
                        return;
                }else{
                        for(int i=0;i<originalStr.length();i++){        //循环遍历整个原始数组
                                if(strCollection.contains(String.valueOf(originalStr.charAt(i)))){        //判断子字符串是否宝海下标为i的原始字符串的字符，如果是就继续循环；没有执行else操作
                                        continue;
                                }else{                                                       
                                        strCollection +=originalStr.charAt(i);                //将子字符串中没有的字符添加到子字符串中
                                        System.out.println(strCollection);                        //打印输出
                                        getCollection(strCollection);                                //进行下一轮迭代
                                        strCollection = strCollection.substring(0, strCollection.length()-1);        //将刚添加到子字符串中的字符去掉。注：我一开始没有考虑到这一步，一直出错
                                }
                        }
                }
        }
       
       
        public static void main(String[] args) {
                Scanner in = new Scanner(System.in);
                Test6 test = new Test6();
                test.originalStr = in.next();
                test.getCollection("");
        }

}
作者: 亲亲    时间: 2014-7-1 10:20
z这道题还真难，好好学习～！
作者: 郑众杰    时间: 2014-7-7 16:06
谢谢，有收获
作者: DSY    时间: 2014-7-18 05:20
还没看到集合   代码看的很辛苦      
作者: 静水流华    时间: 2014-9-25 09:27
我也遇到这道题，来着看看
作者: 杜工    时间: 2014-10-12 08:44
小悠久 发表于 2014-1-6 17:41
import java.util.Scanner;
import java.util.TreeSet;

虽然列出了所有的组合，但是打印出来的有点凌乱。可以在show方法里面用for循环控制下打印的格式，当set中的String长度等于1、2、3时换行，另外再加上双引号就完美了。。。
作者: 15225159271    时间: 2015-7-30 16:20
我试了一下，楼主的做法有点问题
作者: 马塔非耶    时间: 2016-7-7 18:31
String s = "def";
                TreeSet<String> set = new TreeSet<>(new Comparator<String>() { //双列集合去重复
                        public int compare(String s1,String s2) {               
                                int num = s1.length() - s2.length();                //先以长度判断,小的在前
                                return num == 0 ? s1.compareTo(s2) : num;        //在以字典顺序判断;
                        }
                });
                for (int i = 0; i < s.length(); i++) {                                //第一位数
                        for (int j = 0; j < s.length(); j++) {                        //第二位数
                                for (int j2 = 0; j2 < s.length(); j2++) {        //第三位数
                                        set.add(s.charAt(j2) + "");                //将单个字符存进集合,它会自己去重复.
                                        if(s.charAt(j2) == s.charAt(j) | s.charAt(j2) == s.charAt(i) | s.charAt(i) == s.charAt(j)) { //判断三个不能重复
                                                continue;                                                                        //重复就跳出
                                        }else {                                                                                       
                                                set.add(s.charAt(i) + "" + s.charAt(j));                                //否则将两个字符的组合加进集合,它会自己去重复
                                                set.add(s.charAt(j) + "" + s.charAt(j2) + s.charAt(i));                        //将三个字符的组合加进集合,它会自己去重复
                                        }
                                       
                                }
                        }
                }                                                                                                        //遍历集合
                for (String string : set) {
                        System.out.print(string + " ");
                }
        }
}



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