黑马程序员技术交流社区

标题: 这道测试题求高人好方法： [打印本页]

---

作者: 斗神_    时间: 2014-10-15 11:05
标题: 这道测试题求高人好方法：
编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如(这只是个特例)：
原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

---

作者: 二货哈士奇    时间: 2014-10-15 11:05
同学你这样可不好哟，这个不是入学考试的题么。。。。
给你看下我当时提交的答案吧
第六题：        6、 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如：
                        原始字符串是"abc"，打印得到下列所有组合情况：
                        "a" "b" "c"
                        "ab" "bc" "ca" "ba" "cb" "ac"
                        "abc" "acb" "bac" "bca" "cab" "cba"

        答：        思路：
                        1、本题反复的代码在于，判断还剩几个字母没有写，写进去，一直在重复动作，所以考虑用递归，因为要考虑是否包含已有字母，所以用集合作容器
                        2、递归负责做：清空集合，判断哪个没有写，写进集合，打印集合。递归停止标识为不存在没写过的字符，就退出递归
                        3、主函数调用递归函数，给递归一个空的集合。
                        步骤：
                        1、主函数定义一个空集合，将集合传给递归函数
                        2、递归从第一位起开始判断是否已在集合中，不在就写入，存在就不写，继续。用for循环作为递归函数位数的指针，使位数前进
                        3、定义一个打印函数，递归每在集合中写入一个数字，就打印一次
                        import java.util.*;
                        public class d2
                        {
                                static char[] chars="abcd".toCharArray();
                                public static void main(String[] args)
                                {
                                        ArrayList<Integer> list = new ArrayList<Integer>();
                                        play(list);
                                }
                                static void play(List<Integer> list)
                                {
                                        for (int i=0;i<chars.length ;i++ )
                                        {
                                                if(!list.contains(i))
                                                {
                                                        ArrayList<Integer> temp = new ArrayList<Integer>(list);
                                                        temp.add(i);
                                                        show(temp);
                                                        play(temp);
                                                }
                                        }
                                }
                                static void show(ArrayList<Integer> list)
                                {
                                        for(Integer s : list)
                                                System.out.print(chars[s]+"");
                                        System.out.println();

                                }       
                        }

---

作者: 斗神_    时间: 2014-10-15 14:05
没有人会么？~~~

---

作者: 刘树弘    时间: 2014-10-15 22:17

1. public class Traversal {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 new Traversal().traversal('a', 'b', 'c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');
   
5.         }
   
6. 
   
7. 
   
8.         public void traversal(Character... cs) {
   
9.                 List<Character> o = new LinkedList<Character>(Arrays.asList(cs));
   
10.                 List<Character> f = new LinkedList<Character>();
    
11. 
    
12.                 traversal_(o, f);
    
13.         }
    
14. 
    
15.         /**
    
16.          * @param o2  未使用的元素的集合
    
17.          * @param f2 以使用的元素的集合
    
18.          */
    
19.         private void traversal_(List<Character> o2, List<Character> f2) {
    
20.                 println(f2);
    
21.                 for (int i = 0; i < o2.size(); i++) {
    
22.                         LinkedList<Character> o = new LinkedList<Character>(o2);
    
23.                         LinkedList<Character> f = new LinkedList<Character>(f2);
    
24. 
    
25.                         f.add(o.remove(i));
    
26.                         traversal_(o, f);
    
27.                 }
    
28.         }
    
29. 
    
30.         /**
    
31.          * 校验并输出结果
    
32.          */
    
33.         public void println(List<Character> f2) {
    
34.                 if (f2.size() == 0) {
    
35.                         return;
    
36.                 }
    
37.                 char[] cs = new char[f2.size()];
    
38.                 int i = 0;
    
39.                 for (char c : f2) {
    
40.                         cs[i] = c;
    
41.                         i++;
    
42.                 }
    
43. 
    
44.                 System.out.println(new String(cs));
    
45. 
    
46.         }
    
47. }

复制代码

---

作者: 寐海流风    时间: 2014-10-18 20:39
public class StringListThree {
       
        public static void main(String[] args) {
                //传入操作对象，一个字符串
                String str = "abcdefghi";
/*                int len = str.length();
                //字符串转为char[]数组
                char[] ch = str.toCharArray();
               
                TreeSet<String> ts = new TreeSet<>();
                //将字符串每个字符添加进TreeSet<String>
                for(int i=0;i<len;i++){
                        ts.add(String.valueOf(str.charAt(i)));
                }*/
                //做递归运算，次数为操作对象字符串的长度-1
/*                for(int i=1;i<len;i++){
                        addElements(ts,ch);
                }*/
                TreeSet<String> ts = addElementsLast(str);
               
                for(String t:ts){
                        System.out.println(t);
                }
                System.out.println(ts.size());       
        }
        //将原来的方法优化
        public static TreeSet<String> addElementsLast(String str){
               
                int len = str.length();
                char[] ch = str.toCharArray();
               
                TreeSet<String> ts = new TreeSet<>();
                for(int i=0;i<len;i++){
                        ts.add(String.valueOf(str.charAt(i)));
                }

                for(int i=1;i<len;i++){
                        int index = 0;
                       
                        TreeSet<String> tss = new TreeSet<>();
                       
                        for(String t:ts){
                                for(int x=0;x<len;x++){
                                        if(t.length() == i){
                                               
                                                index = t.indexOf(ch[x]);
                                                if(index == -1)
                                                        tss.add(t+ch[x]);
                                        }
                                }
                        }
                       
                        ts.addAll(tss);
                }
                return ts;
        }
}

---

作者: 没劲睡觉    时间: 2014-10-19 19:11
二楼 代码没看懂

---

作者: axing110    时间: 2014-10-19 19:11
怎么不能回复

---

作者: axing110    时间: 2014-10-19 19:18
http://blog.sina.com.cn/s/blog_1351158110102v302.html这里看看吧

---

作者: 十万一千    时间: 2014-10-19 22:14

斗神_ 发表于 2014-10-15 14:05
没有人会么？~~~

分给的太少了啊， 先前我在这个模块提交了很多代码，但是楼主都放鸽子了 哎   

---

作者: axing110    时间: 2014-10-20 09:47
我需要的币少，加我QQ我详细给您解答，主要还是其中的一个递归难点qq:6674784

---

作者: void    时间: 2014-10-21 09:35

1. import java.util.Scanner;
   
2. 
   
3. public class Test {
   
4. 
   
5.         public static void main(String[] args) {
   
6.                 System.out.println("请输入一个字符串");
   
7.                 Scanner in = new Scanner(System.in);
   
8.                 String str = in.nextLine();
   
9.                 System.out.println(str);
   
10.                 int length = str.length() - 1;
    
11.                 System.out.println(length);
    
12.                 for (int i = length; i >= 0; i--) {
    
13.                         for (int j = 0; j < i; j++) {
    
14. 
    
15.                                 System.out.print(String.valueOf(str.charAt(i))
    
16.                                                 + String.valueOf(str.charAt(j)) + "    ");
    
17.                         }
    
18.                         System.out.println();
    
19.                 }
    
20.         }
    
21. }

复制代码

---

作者: void    时间: 2014-10-21 09:37

void 发表于 2014-10-21 09:35

运行结果：
请输入一个字符串
abcd
abcd
3//3为长度-1
da    db    dc   
ca    cb   
ba   

---

作者: java_dream    时间: 2014-10-22 12:28
这片代码绝对能运行成功，并且结果正确：

1. package test;
   
2. 
   
3. import java.util.Random;
   
4. 
   
5. /**
   
6. * 编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如(这只是个特例)：
   
7. * 原始字符串是"abc"，打印得到下列所有组合情况：
   
8. * "a" "b" "c"
   
9. * "ab" "bc" "ca" "ba" "cb" "ac"
   
10. * "abc" "acb" "bac" "bca" "cab" "cba"
    
11. *
    
12. * @author live-dream
    
13. *
    
14. */
    
15. public class Test003 {
    
16.        
    
17.         public static void main(String[] args){
    
18.                 String s = "abcd";
    
19.                 int n = s.length();
    
20.                 int cur = 0;
    
21.                 int positionNumber = 0;
    
22.                
    
23.                 for(int i=1; i<=n; i++){
    
24.                         int denominator = 1;
    
25.                         for(int j=1; j<=n-i; j++){
    
26.                                 denominator *= j;
    
27.                         }
    
28. 
    
29.                         for(int k=0; k<s.length(); k++){
    
30.                                 int[][] ps = getPermutation(s.length(),k,n,i);
    
31.                                 for(int c=0; c<ps.length; c++){
    
32.                                         print(s,ps[c]);
    
33.                                 }
    
34.                         }
    
35.                         System.out.println();
    
36.                 }
    
37.         }
    
38.        
    
39.         public static int[][] getPermutation(int len, int k,int n,int r){
    
40.                 int positionNumber = getPositionNumber(n-1,r-1);
    
41.                 int[][] ps = new int[positionNumber][r];
    
42.                 int[] order = new int[len];
    
43.                
    
44.                 Random random = new Random();
    
45.                
    
46.                 for(int c=0; c<ps.length; c++){
    
47.                         int[] permutation = new int[r];
    
48.                         permutation[0] = k;
    
49.                        
    
50.                         for(int i=1; i<r; i++){
    
51.                                 int randomNum = random.nextInt(n);
    
52.                                         boolean ok = saveNoRepeat(permutation,i,randomNum);
    
53.                                         if(!ok)
    
54.                                                 i--;
    
55.                         }
    
56.                        
    
57.                         boolean ok = false;
    
58.                         for(int j=0; j<c; j++){
    
59.                                 ok = false;
    
60.                                 for(int p=0; p<ps[j].length; p++){
    
61.                                         if(ps[j][p]!=permutation[p])
    
62.                                                 ok = true;
    
63.                                 }
    
64.                                 if(!ok)
    
65.                                         break;
    
66.                         }
    
67.                        
    
68.                         if(c==0)
    
69.                                 ps[c] = permutation;
    
70.                         if(ok){
    
71.                                 ps[c] = permutation;
    
72.                         }else if(!ok && c>0){
    
73.                                 c--;
    
74.                         }
    
75.                 }
    
76.                
    
77.                 return ps;
    
78.         }
    
79.        
    
80.         public static int getPositionNumber(int n, int r){
    
81.                 int positionNumber = 0;
    
82.                 int molecule = 1;
    
83.                 int denominator = 1;
    
84.                
    
85.                 for(int i=1; i<=n; i++){
    
86.                         molecule *= i;
    
87.                 }
    
88.                 for(int i=1; i<=n-r; i++){
    
89.                         denominator *= i;
    
90.                 }
    
91.                 positionNumber = molecule/denominator;
    
92. 
    
93.                 return positionNumber;
    
94.         }
    
95.        
    
96.         public static boolean saveNoRepeat(int[] arr, int index,int value){
    
97.                 boolean noRepeat = true;
    
98.                 for(int i=0; i<index; i++){
    
99.                         if(arr[i]==value){
    
100.                                 noRepeat = false;
     
101.                                 break;
     
102.                         }
     
103.                 }
     
104.                 if(noRepeat)
     
105.                         arr[index] = value;
     
106.                 return noRepeat;
     
107.         }
     
108.        
     
109.         public static void print(String s, int[] permutation){
     
110.                 String test = "";
     
111.                 for(int c=0; c<permutation.length; c++){
     
112.                         test += s.charAt(permutation[c]);
     
113.                 }
     
114.                 System.out.print("\""+test+"\"");
     
115.         }
     
116. 
     
117. }
     

复制代码

---

作者: Forever_Up    时间: 2014-10-23 16:27
还没有解决吗？

---

作者: 计算机小菜鸟    时间: 2014-10-28 23:20
大神好多啊！！！

---

作者: newLife    时间: 2014-11-4 10:11
好题目呀:lol

---

作者: v咔咔    时间: 2014-11-8 22:07
过来学习一下

---

作者: Smart_lll    时间: 2014-11-18 09:39

二货哈士奇 发表于 2014-10-30 16:29
同学你这样可不好哟，这个不是入学考试的题么。。。。
给你看下我当时提交的答案吧
第六题：        6、 编程列出 ...

入学考试题，考这么难啊，菜鸟表示压力山大啊

---

作者: as604049322    时间: 2014-11-22 17:41
import java.util.Scanner;
import java.util.Arrays;
class GetStr {
    public static void main(String[] args) {
        Scanner scanner =new Scanner(System.in);
        System.out.println("请输入欲处理的字符串：");
        String s=scanner.nextLine();
        if(s.equals("")) s="baedyc";
        char[] temp=new char[s.length()];
        for(int i=0;i<s.length();i++)//将字符串分解并保存到数组
            temp[i]=s.charAt(i);
        Arrays.sort(temp);//数组排序
        if(s.length()>=1) result1(temp);
        if(s.length()>=2) result2(temp);
        if(s.length()>=3) result3(temp);
        if(s.length()>=4) result4(temp);
        if(s.length()>=5) result5(temp);
        if(s.length()>=6) result6(temp);
        if(s.length()>=7) result7(temp);
    }
    public static void result1(char[] str)//打印一级组合
    {
        System.out.println("一级组合：");
        String temp="";
        for(int i=0;i<str.length;i++)
                temp=temp+"\""+str[i]+"\" ";
        System.out.println(temp);
    }
    public static void result2(char[] str)//打印二级组合
    {
        System.out.println("二级组合：");
        String temp="";
        for(int i=0;i<str.length-1;i++)
            for(int j=i+1;j<str.length;j++)
                temp=temp+"\""+str[i]+str[j]+"\" ";
        System.out.println(temp);
    }
    public static void result3(char[] str)//打印三级组合
    {
        System.out.println("三级组合：");
        String temp="";
        for(int i=0;i<str.length-2;i++)
            for(int j=i+1;j<str.length-1;j++)
                for(int k=j+1;k<str.length;k++)
                    temp=temp+"\""+str[i]+str[j]+str[k]+"\" ";
        System.out.println(temp);
    }
    public static void result4(char[] str)//打印四级组合
    {
        System.out.println("四级组合：");
        String temp="";
        for(int i=0;i<str.length-3;i++)
            for(int j=i+1;j<str.length-2;j++)
                for(int k=j+1;k<str.length-1;k++)
                    for(int l=k+1;l<str.length;l++)
                        temp=temp+"\""+str[i]+str[j]+str[k]+str[l]+"\" ";
        System.out.println(temp);
    }
    public static void result5(char[] str)//打印五级组合
    {
        System.out.println("五级组合：");
        String temp="";
        for(int i=0;i<str.length-4;i++)
            for(int j=i+1;j<str.length-3;j++)
                for(int k=j+1;k<str.length-2;k++)
                    for(int l=k+1;l<str.length-1;l++)
                        for(int m=l+1;m<str.length;m++)
                            temp=temp+"\""+str[i]+str[j]+str[k]+str[l]+str[m]+"\" ";
        System.out.println(temp);
    }
    public static void result6(char[] str)//打印六级组合
    {
        System.out.println("六级组合：");
        String temp="";
        for(int i=0;i<str.length-5;i++)
            for(int j=i+1;j<str.length-4;j++)
                for(int k=j+1;k<str.length-3;k++)
                    for(int l=k+1;l<str.length-2;l++)
                        for(int m=l+1;m<str.length-1;m++)
                            for(int n=m+1;n<str.length;n++)
                                temp=temp+"\""+str[i]+str[j]+str[k]+str[l]+str[m]+str[n]+"\" ";
        System.out.println(temp);
    }
    public static void result7(char[] str)//打印七级组合
    {
        System.out.println("七级组合：");
        String temp="";
        for(int i=0;i<str.length-6;i++)
            for(int j=i+1;j<str.length-5;j++)
                for(int k=j+1;k<str.length-4;k++)
                    for(int l=k+1;l<str.length-3;l++)
                        for(int m=l+1;m<str.length-2;m++)
                            for(int n=m+1;n<str.length-1;n++)
                                for(int o=n+1;o<str.length;o++)
                            temp=temp+"\""+str[i]+str[j]+str[k]+str[l]+str[m]+str[n]+str[o]+"\" ";
        System.out.println(temp);
    }
}

getstr.zip

2014-11-22 17:41 上传

点击文件名下载附件

861 Bytes, 下载次数: 823

---

作者: 尚勇勇    时间: 2014-11-25 18:49
private static LinkedList<char[]> recursionSub ( int ind, int start )        {                start++;                if (start > count - 1)                {                        return null;                }                for ( indexs[start] = 0; indexs[start] < len; indexs[start]++ )                {                        recursionSub (0, start);                        if (start == count - 1)                        {                                char[] temp = new char[count];                                for ( int i = count - 1; i >= 0; i-- )                                {                                        temp[start - i] = array[indexs[start - i]];                                }                                boolean flag = true;                                for ( int i = 0; i < temp.length; i++ )                                {                                        for ( int j = i+1; j < temp.length; j++ )                                        {                                                if (temp[i] == temp[j])                                                {                                                        flag = false;                                                        break;                                                }                                        }                                }                                if (flag)                                {                                        list.add (temp);                                }                        }                }                return list;        }

---

作者: jdedffjef83j    时间: 2014-11-30 20:36
好难啊，:sleepy:

---

作者: bjznh    时间: 2014-12-16 13:26
跟读，学习一下。哈哈。

---

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

黑马程序员IT技术论坛 X3.2