黑马程序员技术交流社区

标题: 列出一个字符串的全字符组合情况, [打印本页]

---

作者: 木木赤赤    时间: 2013-12-17 11:59
标题: 列出一个字符串的全字符组合情况,


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

---

作者: 豆晨阳    时间: 2013-12-17 13:01
class Demo
{
        public static void main(String[] args)
        {
                String x = "abc";
               
                char x0 = x.charAt(0);
                char x1 = x.charAt(1);
                char x2 = x.charAt(2);
                sop2(x0);
                sop2(x1);
                sop2(x2);
                sop1(x0);sop2(x1);
                sop1(x0);sop2(x2);
                sop1(x1);sop2(x0);
                sop1(x1);sop2(x2);
                sop1(x2);sop2(x0);
                sop1(x2);sop2(x1);
                sop1(x0);sop1(x1);sop2(x2);
                sop1(x0);sop1(x2);sop2(x1);
                sop1(x2);sop1(x1);sop2(x0);
                sop1(x2);sop1(x0);sop2(x1);
                sop1(x1);sop1(x2);sop2(x0);
                sop1(x1);sop1(x0);sop2(x2);
        
        }
        public static String sop1(char y)
        {
                System.out.print(y);
                return null;
        }
        public static void sop2(char z)
        {
                System.out.println(z);
        }
}
本来想加上双引号，没加上

---

作者: 風諾    时间: 2013-12-17 13:39

豆晨阳 发表于 2013-12-17 13:01
class Demo
{
        public static void main(String[] args)

神回复，要是dasgnagnafa咋办？

---

作者: doitforyou    时间: 2013-12-17 14:05

風諾 发表于 2013-12-17 13:39
神回复，要是dasgnagnafa咋办？

确实是神回复。。。
不过万事总要要第一步。

---

作者: 風諾    时间: 2013-12-17 15:10
写了个试试，键盘输入一个字符串，然后返回各种可能。代码如下：

1. package com.itheima.demo;
   
2. 
   
3. import java.util.Scanner;
   
4. import java.util.TreeSet;
   
5. 
   
6. public class Demo1 {
   
7.         public static void main(String[] args) {
   
8.                 Scanner s = new Scanner(System.in);
   
9.                
   
10.                 String str = s.next();
    
11.                 System.out.println(str);
    
12.                
    
13.                 s.close();
    
14.                 show(str);
    
15.                
    
16. 
    
17.         }
    
18.         /**
    
19.          * 打印各种可能
    
20.          * @param str        str是给定的字符串
    
21.          */
    
22.         private static void show(String str) {
    
23.                 TreeSet<String> set = saveInSet(new StringBuilder(str),0,new StringBuilder(),new TreeSet<String>());
    
24.                 for (String s : set) {
    
25.                         System.out.println(s);
    
26.                 }
    
27.         }
    
28.         /**
    
29.          * 返回集合，集合包含字符串所有字符的可能组合
    
30.          * @param str        给定字符串转换成的StringBuilder对象，主要是为了操作字符方便
    
31.          * @param count        计数，对第count进行排列组合
    
32.          * @param buff        暂存放某种可能
    
33.          * @param set        集合，去除重复元素，例如"aab"以第一个a开头会有aba，以第二个a开头也会有aba
    
34.          * @return                返回TreeSet集合
    
35.          */
    
36.         private static TreeSet<String> saveInSet(StringBuilder str, int count, StringBuilder buff, TreeSet<String> set) {
    
37.                 for (int i = 0,len = str.length(); i < len; i++) {
    
38.                         //获取字符
    
39.                         char c = str.charAt(i);
    
40.                         //去掉原字符串的某个字符（保证某个字符不被重复利用）
    
41.                         str.deleteCharAt(i);
    
42.                         //缓存添加该字符
    
43.                         buff.append(c);
    
44.                         //将该种可能组合存入集合
    
45.                         set.add(buff.toString());
    
46.                        
    
47.                         //str仍包含字符，则递归调用，开始取第二位字符
    
48.                         //若还有第三位则继续递归……以此类推
    
49.                         if (str.length() != 0) {
    
50.                                 //count用于记录目前在进行排列组合的第count位
    
51.                                 count++;
    
52.                                 //递归
    
53.                                 saveInSet(str,count,buff,set);
    
54.                                 //第n位递归结束后，需要继续对n-1位排列，位数-1
    
55.                                 count--;
    
56.                         }
    
57.                        
    
58.                         //递归结束后，需要继续对n-1位排列，因此清除第n位的记录
    
59.                         buff.deleteCharAt(count);
    
60.                         //删除的字符插回str
    
61.                         str.insert(i, c);
    
62.                 }
    
63.                 //返回集合
    
64.                 return set;
    
65.                
    
66.         }
    
67. 
    
68. }
    

复制代码

---

作者: 回音    时间: 2013-12-17 15:37
递归+深度优先搜索：
public class Test
{
    public static String str = "abcd";

    public static void main(String[] args)
    {
        Shuffle(0, new String(""));
    }
    public static void Shuffle(int current_recur, String temp)
    {
        if(current_recur < str.length())
        {
            for(int i = 0; i < str.length(); i++)
            {
                if( ! ( temp.contains(str.substring(i, i + 1)) ) )
                {
                    System.out.println(temp + str.substring(i, i + 1));
                    Shuffle(current_recur + 1, new String(temp + str.substring(i, i + 1)));
                }
            }
        }

    }
}

---

作者: 豆晨阳    时间: 2013-12-17 22:06

風諾 发表于 2013-12-17 13:39
神回复，要是dasgnagnafa咋办？

望理解一个java菜鸟的心

---

作者: 風諾    时间: 2013-12-18 13:29

豆晨阳 发表于 2013-12-17 22:06
望理解一个java菜鸟的心

{:3_53:}我理解你

---

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

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