前两天走黑马的流程，遇到一道测试题，自己想了两天才弄一个效率超低的，从网上查了一个答案，居然用了四层循环，看的还不太明白，分享下，希望大神能给我指导指导，有什么更好的方法也希望能告诉小弟，谢谢
6、 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如：
题目：原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"
网上答案：

1. package com.itheima;
   
2. 
   
3. import java.util.LinkedList;
   
4. 
   
5. public class Test12 {
   
6.         static int n=0,count = 0;
   
7.         static char[] array = { 'a', 'b','c','d'};
   
8.         static LinkedList <char[]> list = new LinkedList<char[]> ();//转化为集合
   
9.         static int[] indexs = new int[array.length];
   
10.         static int len = array.length;
    
11. 
    
12.         /**
    
13.          * @param args
    
14.          */
    
15.         public static void main(String[] args) {
    
16.                 // TODO Auto-generated method stub
    
17.                 getSub ();
    
18.                 for ( char[] cs : list ){
    
19.                         System.out.println(cs);
    
20.                         }
    
21.         }
    
22.         private static LinkedList<char[]> getSub ()      //获取
    
23.     {
    
24.         while (count <= len){
    
25.             recursionSub (-1);
    
26.             count++;
    
27.         }
    
28.         return list;
    
29.     }
    
30.         //
    
31.          private static LinkedList <char[]> recursionSub ( int start )
    
32.      {
    
33.          start++;
    
34.          
    
35.          if (start > count - 1){
    
36.                  return null;
    
37.                  }
    
38.          for ( indexs[start] = 0; indexs[start] < len; indexs[start]++ ){
    
39.                  recursionSub (start);
    
40.                  if (start == count - 1){
    
41.                          char[] temp = new char[count];
    
42.                          for ( int i = count - 1; i >= 0; i-- ){
    
43.                                  temp[start - i] = array[indexs[start - i]];
    
44.                                  }
    
45.                          boolean flag = true;
    
46.                          for ( int i = 0; i < temp.length; i++ ){
    
47.                                  for ( int j = i+1; j < temp.length; j++ ){
    
48.                                          if (temp[i] == temp[j]){
    
49.                                                  flag = false;
    
50.                                                  break;
    
51.                                                  }
    
52.                                          }
    
53.                                  }
    
54.                          if (flag){
    
55.                                  list.add (temp);
    
56.                                  }
    
57.                          }
    
58.                  }
    
59.          return list;
    
60.          }
    
61. }
    

复制代码

弄个数组，按1个，2个，3个，遍历。

HPU--spring87 发表于 2014-7-23 21:21
弄个数组，按1个，2个，3个，遍历。

输入的字符串长度不一定是3，可能是4,5………………10000000000

每次看到这题我都会重新写一遍。

1. package test;
   
2. 
   
3. public class Test5 {
   
4.        
   
5.         public static void main(String[] args) {
   
6.                 printStringCombination("abcd");
   
7.         }
   
8.         //封装一下
   
9.         public static void printStringCombination(String string){
   
10.                 String[] selected = {""};//初始化已选择字符串数组
    
11.                 String[] toSelect = {string};//初始化待选择字符串数组
    
12.                 combine(selected, toSelect, string.length());//开始选择
    
13.         }
    
14.         //打印组合的具体实现，需要递归
    
15.         private static void combine(String[] selected,String[] toSelect,int length) {
    
16.                 if(length==0){//length为待选择字符串的长度，长度为0则退出方法
    
17.                         return;
    
18.                 }
    
19.                 /*
    
20.                  * ------------初始------------
    
21.                  * 已选择：空串                对应未选择:abc
    
22.                  * ------------选第一个------------
    
23.                  * 已选择：                对应未选择：
    
24.                  * a                        bc
    
25.                  * b                        ac
    
26.                  * c                        ab                共 1*3=3种
    
27.                  * ------------选第二个------------
    
28.                  * 已选择：                对应未选择：
    
29.                  * ab                        c
    
30.                  * ac                        b
    
31.                  * ba                        c
    
32.                  * bc                        a
    
33.                  * ca                        b
    
34.                  * cb                        a                共 3*2=6种
    
35.                  * 每次选择得到的组合数为 上次已经选择的组合数*待选择字符串的长度
    
36.                  */
    
37.                 int combinations = selected.length*length;//每次选择得到的组合数
    
38.                 String[] newSelected = new String[combinations];//新一轮已选择的组合
    
39.                 String[] newToSelect = new String[combinations];//新一轮待选择的组合
    
40.                 int count = 0;
    
41.                 for (int i = 0; i < selected.length; i++) {
    
42.                         for (int j = 0; j < length; j++) {
    
43.                                 newSelected[count] = selected[i]+toSelect[i].charAt(j);//选择一个字符拼接到已选择字符串上
    
44.                                 //把选择的字符从原待选择字符串中剔除
    
45.                                 newToSelect[count] = toSelect[i].substring(0,j)+toSelect[i].substring(j+1);
    
46.                                 System.out.print(newSelected[count++]+" ");//打印最新得到的组合
    
47.                         }
    
48.                 }
    
49.                 System.out.println();//换行
    
50.                 combine(newSelected, newToSelect, length-1);//递归进行一下次选择
    
51.         }
    
52. }
    

复制代码

受教了，也在看这个题

花花公子 发表于 2014-7-23 22:59
受教了，也在看这个题

与君共勉

最基础的应该是用数组吧，利用length确定实际个数

1. package com.itheima;
   
2. import java.util.Scanner;
   
3. /**
   
4. * 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，
   
5. * 例如：原始字符串是"abc"，打印得到下列所有组合情况
   
6. * "a" "b" "c"
   
7. * "ab" "bc" "ca" "ba" "cb" "ac"
   
8. * "abc" "acb" "bac" "bca" "cab" "cba"
   
9. * @author dong
   
10. *
    
11. */
    
12. public class Test6 {
    
13.         private String input;                //从输入流中读取的字符串        
    
14.     private void getCollection(String strCollection)
    
15.     {
    
16.       if(strCollection.length() == input.length()){
    
17.                     return;              //当迭代到子字符串和原始字符串相同长度时，迭代结束，返回
    
18. }
    
19.        else{
    
20.                for(int i=0;i<input.length();i++){        //循环遍历整个原始数组
    
21.                if(strCollection.contains(String.valueOf(input.charAt(i)))){    //判断子字符串是否包含下标为i的原始字符串的字符，如果是就继续循环；没有执行else操作
    
22.                continue;
    
23.            }
    
24.        else{                                                        
    
25.                 strCollection +=input.charAt(i);                //将子字符串中没有的字符添加到子字符串中
    
26.                 System.out.println(strCollection);              //打印输出
    
27.                 getCollection(strCollection);                   //进行下一轮迭代
    
28.                 strCollection = strCollection.substring(0, strCollection.length()-1);//将刚添加到子字符串中的字符去掉。
    
29.             }
    
30.           }
    
31.        }
    
32.     }
    
33.      public static void main(String[] args) {
    
34.                 System.out.println("请输入字符串");
    
35.                 Scanner in = new Scanner(System.in);
    
36.             Test6 test = new Test6();
    
37.             test.input = in.next();
    
38.             test.getCollection("");
    
39.     }
    
40. }
    

复制代码

学习了，很不错，多发这种帖子

明早试做看

三重循环，无递归。

1. import java.util.ArrayList;
   
2. 
   
3. /*
   
4. * 输入N个字符,如'a','b','c'，打印出所有组合
   
5. * a b c
   
6. * ab ac bc ba bc cb
   
7. * abc acb bac bca cba cab
   
8. *
   
9. * 思路：
   
10. *   长度为n的字符串排列，是长度为n-1的每个字符串排列的末尾加上一个字符
    
11. *   比如，abc是由ab末尾加c得到的；acb是由ac末尾加c得到的。
    
12. *   因此，用一个ArrayList不断添加已得到的排列结果。当要排列长度为n的字符串时，让两个指针分别指向长度为n-1的排列在结果集合中的起止下标
    
13. */
    
14. 
    
15. public class Permute {
    
16. 
    
17.         public static void main(String[] args) {
    
18. 
    
19.                 String s = "abc";
    
20.                 printPermute(s);
    
21.         }
    
22.         
    
23.         public static void printPermute(String str) {
    
24.                 char[] candidates = str.toCharArray();
    
25.                 int len = str.length();
    
26.                 ArrayList<String> permutations = new ArrayList<String>(); // 存储排列结果
    
27.                 // 长度为1的排列，直接添加
    
28.                 for (char c : candidates)
    
29.                         permutations.add(Character.toString(c));
    
30.                 // 下标指针，分别指向长度为1的字符串排列的起止位置
    
31.                 int start = 0;
    
32.                 int end = permutations.size();
    
33. 
    
34.                 // 长度2到len的排列，用循环完成
    
35.                 for (int i = 2; i <= len; i++) {
    
36.                         // 下面的二重循环，外层循环遍历长度为n-1的每一个字符串排列
    
37.                         for (; start < end; start++) {
    
38.                                 String s = permutations.get(start);
    
39.                                 // 内层循环则尝试在长度为n-1的字符串排列的尾部添加一个字符，形成一个长度为n的字符串
    
40.                                 for (char c : candidates) {
    
41.                                         // 只添加不重复的字符
    
42.                                         if (s.indexOf(c) == -1)
    
43.                                                 permutations.add(s + c);
    
44.                                 }
    
45.                         }
    
46.                         // 经过循环，start已经指向长度为n-1的字符串排列在结果集合中的起始位置
    
47.                         // 现在让end指向指向长度为n-1的字符串排列在结果集合中的终止位置
    
48.                         end = permutations.size();
    
49.                         // 开始下一次循环，处理长度为n的字符串排列
    
50.                 }
    
51.                
    
52.                 // 打印结果集合及其元素个数
    
53.                 System.out.println(permutations);
    
54.                 System.out.println(permutations.size());
    
55.         }
    
56. }
    

复制代码

这个问题，貌似做过

我也有这个题目 呵呵

升级一下我4楼中的算法，这下不用递归了，直接通过while循环搞定，只要定义一个方法就OK。

1. package test;
   
2. 
   
3. public class CopyOfTest5 {
   
4. 
   
5.         public static void main(String[] args) {
   
6.                 printStringCombination("abcdef");
   
7.         }
   
8. 
   
9.         public static void printStringCombination(String string) {
   
10.                 String[] selected = { "" };
    
11.                 String[] toSelect = { string };
    
12.                 int length = string.length();
    
13.                 int combinations;// 每次选择得到的组合数
    
14.                 while (length != 0) {
    
15.                         combinations = selected.length * length;
    
16.                         String[] newSelected = new String[combinations];// 新一轮已选择的组合
    
17.                         String[] newToSelect = new String[combinations];// 新一轮待选择的组合
    
18.                         for (int i = 0, count = 0; i < selected.length; i++) {
    
19.                                 for (int j = 0; j < length; j++, count++) {
    
20.                                         newSelected[count] = selected[i] + toSelect[i].charAt(j);// 选择一个字符拼接到已选择字符串上
    
21.                                         if (length != 1) {// 当待选择数组中的字符串长度为1的时候，就不需要再更改该组合了
    
22.                                                 newToSelect[count] = toSelect[i].substring(0, j)
    
23.                                                                 + toSelect[i].substring(j + 1);
    
24.                                         }
    
25.                                         System.out.print(newSelected[count] + "\t");// 打印最新得到的组合
    
26.                                 }
    
27.                         }
    
28.                         System.out.println();
    
29.                         selected = newSelected;// 更新已选择组合
    
30.                         toSelect = newToSelect;// 更新待选择组合
    
31.                         length--;// 待选择组合中的字符串长度减1
    
32.                 }
    
33.         }
    
34. }
    

复制代码

fantacyleo 发表于 2014-7-24 00:46
三重循环，无递归。

我也重写了下。在14楼。

赞一个。。。。。。。。