A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© striker 中级黑马   /  2014-10-25 14:36  /  1839 人查看  /  6 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

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

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

6 个回复

倒序浏览
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());
        }
}


楼主,共同学习

回复 使用道具 举报
我来提供一种思路,非原创,借鉴网上文章。代码如下:
  1. import java.util.ArrayList;
  2. import java.util.List;

  3. public class Combinations {

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

  33. }
复制代码

需要说明的在代码中添加了注释,我的结果包含'a,b,c'都不选的情况。
回复 使用道具 举报
你是怎么把代码插入到博客中的呀?
回复 使用道具 举报
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);
                                }
                        }
                }
        }
}

回复 使用道具 举报
  1. package test;

  2. import java.util.Random;

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

  113. }
复制代码
回复 使用道具 举报
zhappy 中级黑马 2014-10-26 08:39:06
7#
基础题不简单呀
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马