编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符,
例如：原始字符串是"abc"，
打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

第二行如下：ab ac ba bc  ca  cb
1.定义一个数组
2.两个for循环嵌套
3一个 变量x  一个变量y分别是两个for的变量
4.int x =0 ; x<3;x++  .int y =0;y<3;y++;
5 内循环中 if (x==y) continue  跳过这次循环  否则输出 两个字符组合
第三行 类似；
三个循环嵌套  最内循环 if(x==y||x==z||y==z) continue

关键是两个算法，
1.组合算法（递归）把N个字符组成的字符串从头到尾依次去掉一个字符，形成N种组合，在对形成的组合递归使用该方法，问题是同一次生成的子串再次递归时，生成的组合会有重复的，因此这个最好推荐map，省掉去重。比如abc第一次递归生成bc,ac,ab，第二次递归生生成(b,c),(a,c),(a,b)，第二次就产生了重复的组合。这个比较简单，复杂点的是排列的算法，需要对生成的组合调用排列算法，这个算法也是递归的。
2.排列算法，根据排列的定义，从N个字符中任取一个与剩下的去掉该字符的字符串重新组合，有N中可能，对剩下的没有被选择过的n-1个字符形成的串递归这个方法，于是就有了N!种排列。需要循环从没被选择过的字符串里依次取出一个字符，之后将这个字符从原串去掉，建议用StringBuilder的replace(int start, int end, '')方法，将已经被选择过的字符，取出的字符与去掉字符的串三者重新组合，并将结果加入结果集，递归这个方法，得到字符串所有排列。
3.结果集的处理，建议全部用map，在输出的时候格式化一下，通过循环将长度一样的字符串显示在一行。

不会，不过看完这个我想到了个递归...但是怎么组合不会.....等级太低

冒牌高手 发表于 2014-8-7 19:05
不会，不过看完这个我想到了个递归...但是怎么组合不会.....等级太低

我也想到了递归，但是不会用呀

bbdeyouxang 发表于 2014-8-6 23:50
关键是两个算法，
1.组合算法（递归）把N个字符组成的字符串从头到尾依次去掉一个字符，形成N种组合，在对 ...

谢谢你的解释。。。

建议不要去使用递归，递归是过去现在以及将来被几乎所有程序员规避的东西
假如，你是在排列一个很长的字符串，就30个字符吧，很可能即使你的程序一点问题都没有，但是它就是栈溢出，没办法，递归的太深了

这道题是可以用非递归的方式做的
你要做的是：
1.顺次获取字符串的每一个排列方式
2.判断方式是不是你需要的
3.输出当前的排列

你可以这么想，假如，一个三位的字符串，里面有3种字符（各不相同）
故，你的排列长度最小是1，最大是3
对于每一种长度（以3为例），你可以将它当成一个3位的，每一位最多有三种情况的三位3进制数，从这个三位数的最小值开始，遍历到其最大值，每一个数都是一个排列的状态

希望上面的对你有用，这个题三言两语说不清楚。

基础题吧！！！我也抽到了这道

zeus00456 发表于 2014-8-9 14:25
建议不要去使用递归，递归是过去现在以及将来被几乎所有程序员规避的东西
假如，你是在排列一个很长的字符 ...

谢谢您的解释，我正在努力做

李利威 发表于 2014-8-9 21:33
基础题吧！！！我也抽到了这道

我就差这道题了，其他基础题，我全做出来。。。

我也抽到了这道题，做了老久，lz加油！

我今天做了下这道题。确实好麻烦。
我一开始只想到了递归方法（水平有限，实在没办法）。在参考了7楼zeus00456兄的思路后，写了非递归方法。
下面是我的代码，仅供参考：

1. import java.util.ArrayList;
   
2. import java.util.HashSet;
   
3. import java.util.List;
   
4. import java.util.Set;
   
5. import java.util.regex.Matcher;
   
6. import java.util.regex.Pattern;
   
7. 
   
8. public class StringDemo {
   
9. 
   
10.         public static void main(String[] args) {
    
11.                 String str="abcd";
    
12.                 //方法一：递归方法
    
13.                 List<String> subStrs=getSubStr(str);//获取所有的子串
    
14.                 List<String> stringSet=new ArrayList<String>();//用于添加所有的排列组合
    
15.                 //获取每个子串的排列情况并添加进stringSet
    
16.                 for(String string:subStrs){
    
17.                         List<String> oldSet=arrangeStr(string,string.length());
    
18.                         for(String arrangedStr:oldSet){
    
19.                                 stringSet.add(arrangedStr);
    
20.                         }
    
21.                 }
    
22.                 System.out.println(stringSet);
    
23.                
    
24.                 //方法二：非递归方法
    
25.                 /*char[] chs=str.toCharArray();
    
26.                 List<String> stringSet=new ArrayList<String>();
    
27.                 int len=str.length();
    
28.                 //获取所有的排列组合
    
29.                 for (int i = 1; i <= len; i++) {
    
30.                         Set<String> oldSet=getArrangedStr(chs,i);
    
31.                         for(String string:oldSet){
    
32.                                 stringSet.add(string);
    
33.                         }
    
34.                 }
    
35.                 System.out.println(stringSet);*/
    
36.         }
    
37.         //方法一：递归方法
    
38.         //找出该字符串的所有子串
    
39.         private static List<String> getSubStr(String str) {
    
40.                 List<String> newSet=new ArrayList<String>();       
    
41.                 for (int i = 1; i <= str.length(); i++) {       
    
42.                         List<String> oldSet=subStr(str,i);
    
43.                         for (String string:oldSet) {
    
44.                                 newSet.add(string);                       
    
45.                         }
    
46.                 }
    
47.                 return newSet;
    
48.         }
    
49.         //获取num长度的子串
    
50.         private static List<String> subStr(String str,int num){
    
51.                 List<String> newSet=new ArrayList<String>();
    
52.                 //如果要求子串长度为1，则每个字母都是子串
    
53.                 if(num==1){
    
54.                         for(int i=0;i<str.length();i++){
    
55.                                 newSet.add(str.charAt(i)+"");
    
56.                         }
    
57.                         return newSet;
    
58.                 }
    
59.                 //如果要求子串长度为n，在确定首字母的情况下，递归获取剩下n-1位子串，然后拼凑起来
    
60.                 for(int i=0;i<str.length()-1;i++){
    
61.                         char c=str.charAt(i);
    
62.                         List<String> oldSet=subStr(str.substring(i+1),num-1);
    
63.                         for(String string:oldSet){
    
64.                                 newSet.add(c+string);
    
65.                         }
    
66.                 }
    
67.                 return newSet;
    
68.         }
    
69.         //排列字符串
    
70.         private static List<String> arrangeStr(String str,int len) {
    
71.                 List<String> newSet=new ArrayList<String>();       
    
72.                 //如果字符串长度为1，则该字符串就只有一种排列情况
    
73.                 if(len==1){
    
74.                         newSet.add(str);
    
75.                         return newSet;
    
76.                 }
    
77.                 //如果字符串长度为n，在确定首字母的情况下，递归获取剩下n-1长度的字符串的排列情况，然后拼凑起来
    
78.                 for (int i = 0; i < len; i++) {
    
79.                         StringBuilder sb=new StringBuilder(str);
    
80.                         char c=sb.charAt(i);
    
81.                         List<String> oldSet=arrangeStr(sb.deleteCharAt(i).toString(),len-1);
    
82.                         for (String string:oldSet) {
    
83.                                 newSet.add(c+string);                       
    
84.                         }
    
85.                 }
    
86.                 return newSet;
    
87.         }
    
88.         //方法二：非递归方法
    
89.         //获取长度为i的子串的所有排列情况
    
90.                 private static Set<String> getArrangedStr(char[] chs, int i) {
    
91.                         Set<String> hs=new HashSet<String>();
    
92.                         /*对于每一种长度i，将它当成一个i位的，
    
93.                         每一位有chs.length种情况的chs.length进制数，
    
94.                         从这个0开始遍历到最大值，每一个数都是一种排列情况*/
    
95.                         for (int j = 0; j < Math.pow(chs.length, i); j++) {
    
96.                                 StringBuilder sb=new StringBuilder();
    
97.                                 String string=Integer.toString(j, chs.length);//转换成chs.length进制值
    
98.                                 string=String.format("%0"+i+"d", Integer.parseInt(string));//前面补0,保证字符串都是i位的
    
99.                                 //产生一种排列情况，即一个子串
    
100.                                 for (int k = 0; k < string.length(); k++) {
     
101.                                         sb.insert(0,chs[Integer.parseInt(""+string.charAt(k))]);
     
102.                                 }
     
103.                                 String newStr=sb.toString();
     
104.                                 //去除包含重复字母的子串
     
105.                                 if(checkStr(newStr))
     
106.                                         hs.add(sb.toString());
     
107.                                 else
     
108.                                         continue;
     
109.                         }
     
110.                         return hs;
     
111.                 }
     
112.                 //判断子串是否包含重复字母
     
113.                 private static boolean checkStr(String newStr) {
     
114.                         String regex="(\\w)\\w*\\1+";
     
115.                         Pattern pattern=Pattern.compile(regex);
     
116.                         Matcher matcher=pattern.matcher(newStr);
     
117.                         return !matcher.find();
     
118.                 }
     
119. }
     

复制代码