黑马程序员技术交流社区

标题: 全字母组合问题 [打印本页]

---

作者: striker    时间: 2014-10-25 14:36
标题: 全字母组合问题
Java基本测试题中有一个全字母组合问题。
编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符,
例如：原始字符串是"abc"，
打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

针对这个问题，我做了一些思考。任意一个字符串，先把它分成一个个字符，并存入一个数组A。就是一个字符的全组合。
然后到两个字符进行全排时，把数组A的每个元素都默认放在第一位，后面依次放上A中其余的元素就可以了。得集合B
到三个字符进行排时，把数组A的每个元素都默认放在第一位，后面依次跟上B中的每一个元素就可以了。得集合C
..
..
..
依次递归到全部字符。但不知道如何实现。请各位高手指教！

---

作者: 紫薰iy    时间: 2014-10-25 16:50
package com.ming.test.test9999;

import java.util.ArrayList;
import java.util.List;

public class Test10 {
        //需要排列的字符串
        static String string = "ming";
        //记录上一次排列中的所有的组合
        static List<String> list = new ArrayList<String>();
        //临时的数组，用于比较
        static List<String> temp = new ArrayList<String>();

        public static void main(String[] args) {
                init();
                printList(list);

                if (string.length() > 1) {
                        int index = 2;
                        //排序的大小，最多为字符串的长度
                        while (index <= string.length()) {
                                for (int i = 0; i < list.size(); i++) {
                                        for (int j = 0; j < string.length(); j++) {
                                               
                                                //list中元素有没有包含string中的字符，没有就加上
                                                if (!list.get(i).contains(string.charAt(j) + "")) {
                                                        temp.add(list.get(i) + string.charAt(j));
                                                }
                                        }
                                }
                                copyValue();
                                printList(list);
                               
                                index++;
                        }
                }

        }
        //赋值，将temp中的元素传给list。清空之后在赋值，不能用等号直接赋值
       
       
        ////////////////////////////////////
        //在这里耽误的时间比较多一些，因为我用的是=直接赋值，可是后面又将temp清空，
        //导致list不能记录上次中的记录。因为在这里=是引用的意思吧。
        //list随着temp的改变而改变，并未起到真正的赋值
        ////////////////////////////////////
        public static void copyValue(){
                list.clear();
                for (int i = 0; i < temp.size(); i++) {
                        list.add(temp.get(i));
                }
                temp.clear();
        }
        //初始化，将list中的第一次中都为一个字符
        public static void init() {
                for (int i = 0; i < string.length(); i++) {
                        list.add(string.charAt(i) + "");
                }
        }

        public static void printList(List<String> list) {
                System.out.println(list.toString());
        }
}


楼主，共同学习

---

作者: yueyazhishang    时间: 2014-10-25 17:59
我来提供一种思路，非原创，借鉴网上文章。代码如下：

1. import java.util.ArrayList;
   
2. import java.util.List;
   
3. 
   
4. public class Combinations {
   
5. 
   
6. /*  
   
7. * 设有n个元素，组合数量有2的n次方种。
   
8. * 对 0 到 2的n次方-1 中的每个数，考察其二进制位形式，位数为1代表相应元素加入到组合，0则不加入该元素至组合。
   
9. */
   
10. public static List<List<Object>> getCombinations(List<Object> list) {
    
11.     List<List<Object>> result = new ArrayList<List<Object>>();
    
12.     long n = (long)Math.pow(2,list.size());//2的n次方；8
    
13.     List<Object> combine;//定义一个list，用于存放合理的一种情况，之后将合理的组合放入到结果集中
    
14.     for (long l=0L; l<n; l++) {//0 - 7
    
15.         combine = new ArrayList<Object>();
    
16.         for (int i=0; i<list.size(); i++) {//0 - 2
    
17.             if (((l>>>i)&1) == 1)//八种情况每种情况右移i位，取最后位的值，如果末位置为1则将该元素加入到结果集中，如果为0则不加入
    
18.                 combine.add(list.get(i));
    
19.         }
    
20.         result.add(combine);
    
21.     }
    
22.     return result;
    
23. }
    
24. public static void main(String[] args) {
    
25.     ArrayList<Object> list = new ArrayList<Object>();
    
26.     //将所需要组合排序的元素加入到集合中
    
27.     list.add("a");
    
28.     list.add("b");
    
29.     list.add("c");
    
30.     //定义一个List，用于存放结果集，结果集是一个list。所以是一个嵌套list
    
31.     List<List<Object>> result = getCombinations(list);
    
32.     System.out.println(list.toString());
    
33.     System.out.println(result.toString());
    
34. }
    
35. 
    
36. }
    

复制代码

需要说明的在代码中添加了注释，我的结果包含'a,b,c'都不选的情况。

---

作者: striker    时间: 2014-10-25 18:53
你是怎么把代码插入到博客中的呀？

---

作者: 香草芭芙    时间: 2014-10-25 23:36
package test;

import java.util.*;

public class Test24
{
        public static void main(String[] args)
        {
                String test = "abc";
                TreeSet<String> set = new TreeSet<String>();
                method(test, set);
                for (int i = 1; i <= test.length(); i++)
                {
                        for (String s : set)
                        {
                                if (s.length() == i)
                                        System.out.print("\"" + s + "\"" + "\t");
                        }
                        System.out.println();
                }
        }
        public static void method(String test, TreeSet<String> set)
        {
                for (int x = 0; x < test.length(); x++)
                {
                        test.charAt(x);
                        String ssss = test.charAt(x) + "";
                        set.add(ssss);
                        for (int y = 0; y < test.length(); y++)
                        {
                                if (y == x)
                                        continue;
                                test.charAt(y);
                                String sss = test.charAt(x) + "" + test.charAt(y);
                                set.add(sss);
                                for (int z = 0; z < test.length(); z++)
                                {
                                        if (z == x || z == y)
                                                continue;
                                        test.charAt(z);
                                        String ss = test.charAt(x) + "" + test.charAt(y) + test.charAt(z);
                                        set.add(ss);
                                }
                        }
                }
        }
}

---

作者: java_dream    时间: 2014-10-25 23:55

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 = "abcde";
    
19.                 int n = s.length();
    
20.                
    
21.                 for(int i=1; i<=n; i++){
    
22.                         int[][] permutations = permutationResults(n,i);
    
23.                        
    
24.                         for(int j=0; j<permutations.length; j++){
    
25.                                 print(s,permutations[j]);
    
26.                         }
    
27.                         System.out.println();
    
28.                 }
    
29.         }
    
30.        
    
31.         public static int[][] permutationResults(int n,int r){
    
32.                 int[][] permutations = null;
    
33.                 int resultCount = 0;
    
34.                 int molecule = 1;
    
35.                 int denominator = 1;
    
36.                
    
37.                 for(int i=1; i<=n; i++){
    
38.                         molecule *= i;
    
39.                 }
    
40.                
    
41.                 for(int i=1; i<=n-r; i++){
    
42.                         denominator *= i;
    
43.                 }
    
44.                
    
45.                 resultCount = molecule/denominator;
    
46.                 permutations = new int[resultCount][r];
    
47.                
    
48.                 Random random = new Random();
    
49.                 for(int i=0; i<permutations.length; i++){
    
50.                        
    
51.                         for(int j=0; j<permutations[i].length; j++){
    
52.                                 int rand = random.nextInt(n);
    
53.                                
    
54.                                 if(j==0)
    
55.                                         permutations[i][j] = rand;
    
56.                                
    
57.                                 if(j>0){
    
58.                                 boolean isSave = saveEle_no_repeat(permutations[i],j,rand);
    
59.                                 if(!isSave)
    
60.                                         j--;
    
61.                                 }
    
62.                         }
    
63.                        
    
64.                         if(i>0){
    
65.                         boolean isSave = saveArr_no_repeat(permutations, i,permutations[i]);
    
66.                         if(!isSave)
    
67.                                 i--;
    
68.                         }
    
69.                 }
    
70.                
    
71.                 return permutations;
    
72.         }
    
73.        
    
74.         public static boolean saveEle_no_repeat(int[] permutation, int index, int value){
    
75.                 boolean isSave = true;
    
76.                 for(int i=0; i<index; i++){
    
77.                         if(permutation[i]==value){
    
78.                                 isSave = false;
    
79.                                 break;
    
80.                         }
    
81.                 }
    
82.                
    
83.                 if(isSave)
    
84.                         permutation[index] = value;
    
85.                
    
86.                 return isSave;
    
87.         }
    
88.        
    
89.         public static boolean saveArr_no_repeat(int[][] permutations, int index, int[] permutation){
    
90.                 boolean isSave = false;
    
91.                 for(int i=0; i<index; i++){
    
92.                         isSave = false;
    
93.                         for(int j=0; j<permutations[i].length; j++){
    
94.                                 if(permutations[i][j]!=permutation[j])
    
95.                                         isSave = true;
    
96.                         }
    
97.                        
    
98.                         if(!isSave)
    
99.                                 break;
    
100.                 }
     
101. //               
     
102. //                if(isSave)
     
103. //                        permutations[index] = permutation;
     
104.                
     
105.                 return isSave;
     
106.         }
     
107.        
     
108.         public static void print(String s, int[] arr){
     
109.                 String result = "";
     
110.                 for(int i=0; i<arr.length; i++){
     
111.                         result += s.charAt(arr[i]);
     
112.                 }
     
113.                 System.out.print("\""+result+"\"");
     
114.         }
     
115. 
     
116. }
     

复制代码

---

作者: zhappy    时间: 2014-10-26 08:39
基础题不简单呀

---

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

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