黑马程序员技术交流社区

标题: 一道java练习题 [打印本页]
作者: 294645832    时间: 2014-5-24 15:27
标题: 一道java练习题
本帖最后由 294645832 于 2014-6-5 15:25 编辑

编程列出一个字符串的全字符组合情况，原始字符串中没有重复字符，例如：


原始字符串是"abc"，打印得到下列所有组合情况：
"a" "b" "c"
"ab" "bc" "ca" "ba" "cb" "ac"
"abc" "acb" "bac" "bca" "cab" "cba"

关于这个 我只想到了一个不是办法的办法 ，但是一但少于或者多于三个就不行了，哪位师兄帮忙解答一下，麻烦将步骤写详细一点 谢谢
  1. public class Test8 {
  2.         public static void main(String[] args) {
  3.                 char[] ch = "abc".toCharArray();
  4.                
  5.                 for(int x = 0;x<ch.length;x++){
  6.                         System.out.println(ch[x]);
  7.                         for(int y=0;y<ch.length;y++){
  8.                                 if(x!=y){
  9.                                         System.out.println(ch[x]+""+ch[y]);
  10.                                         for(int z=0;z<ch.length;z++){
  11.                                                 if(y!=z){
  12.                                                         
  13.                                                         System.out.println(ch[x]+""+ch[y]+""+ch[z]);
  14.                                                 }
  15.                                         }
  16.                                 }
  17.                         }
  18.                 }
复制代码




作者: e10my    时间: 2014-5-24 17:43
本帖最后由 e10my 于 2014-5-24 17:50 编辑
  1. /**
  2. * @author e10my
  3. * 显示出一个字符串的所有排列组合.
  4. * 例:
  5. * 原始字符串是"abc"，打印得到下列所有组合情况：
  6. *        "a" "b" "c"
  7. *        "ab" "bc" "ca" "ba" "cb" "ac"
  8. *        "abc" "acb" "bac" "bca" "cab" "cba"
  9. */
  10. public class PaiLie {
  11.         
  12.         public void runPermutation(char[] a, int n) {
  13.                
  14.                 if(null == a || a.length == 0 || n <= 0 || n > a.length)
  15.                         return;
  16.                         
  17.                 char[] b = new char[n];//辅助空间，保存待输出组合数
  18.                 getCombination(a, n , 0, b, 0);
  19.         }

  21.         public void getCombination(char[] a, int n, int begin, char[] b, int index) {
  22.                
  23.                 if(n == 0){//如果够n个数了，输出b数组
  24.                         
  25.                         getAllPermutation(b,0);//得到b的全排列
  26.                         return;
  27.                 }
  28.                         
  29.                 for(int i = begin; i < a.length; i++){
  30.                         
  31.                         b[index] = a[i];
  32.                         getCombination(a, n-1, i+1, b, index+1);
  33.                 }
  34.                
  35.         }
  36.         public void getAllPermutation(char[] a,int index){

  38.                 /*与a的元素个数相同则输出*/
  39.                 if(index == a.length-1){
  40.                         System.out.print("\'");
  41.                         for(int i = 0; i < a.length; i++){
  42.                                 System.out.print(a[i]);
  43.                         }
  44.                         System.out.print("\' ");
  45.                         return;
  46.                 }
  47.                
  48.                 for(int i = index; i < a.length; i++){
  49.                         
  50.                         swap(a ,index, i);
  51.                         getAllPermutation(a, index+1);
  52.                         swap(a ,index, i);
  53.                 }
  54.         }
  55.         public void swap(char[] a, int i, int j) {
  56.         
  57.                 char temp = a[i];
  58.                 a[i] = a[j];
  59.                 a[j] = temp;
  60.         }
  61.         public static void main(String[] args){
  62.                
  63.                 PaiLie robot = new PaiLie();
  64.                 String str = "abc";
  65.                 char[] a = str.toCharArray();
  66.                 //int[] a = {1,2,3};
  67.                 //int n = 2;
  68.                 for(int i = 0; i<=str.length();i++){
  69.                 robot.runPermutation(a,i);
  70.                 System.out.println( );
  71.                 }

  73.         }

  75. }
复制代码

这道题很有意思, 想了好长时间也没有想到思路.最终还是引用了@nash_的一个算法
via : http://blog.csdn.net/zmazon/article/details/8351611




以上代码经过源代码改善得到.请慎重参考.

如果可以找到更好的方法, 希望共同探讨.



作者: 木华    时间: 2014-5-24 17:49
       我把你的程序改了一下，1,2,3，时都可以了。如果为四个的时候就需要再添加for循环语句。
class Test8
{
        public static void main(String[] args)
    {
                char[] ch = "ab".toCharArray();
               
                int i,j,k;
            for(int m=1; m<=ch.length;m++)
             {
             if(m==1)
               {
                 for(i=0;i<ch.length;i++)
                {
                 System.out.println(ch[i]);
                 }
                }
                   if(m==2)
                         {
                             for(i=0;i<ch.length;i++)
                             {
                               for(j=0;j<ch.length;j++)  
                               {
                                if(i==j) continue;
                                System.out.println(ch[i]+""+ch[j]);
                                }
                              }
                         }

                      if(m==3)
                     {
                     for(i=0;i<ch.length;i++)
                       {
                               for(j=0;j<ch.length;j++)
                           {   
                              for(k=0;k<ch.length;k++)
                               {  
                               if (i==j) continue;
                               if(i==k) continue;
                               if(j==k) continue;
                               System.out.println(ch[i]+""+ch[j]+""+ch[k]);


                                }
                            }
                         }


                      }
      }
}
}
作者: e10my    时间: 2014-5-24 17:54
木华 发表于 2014-5-24 17:49
我把你的程序改了一下，1,2,3，时都可以了。如果为四个的时候就需要再添加for循环语句。
class Test ...


如果5,6 个String 长度的话 程序将变得很难解读.
作者: 木华    时间: 2014-5-24 18:01
e10my 发表于 2014-5-24 17:54
如果5,6 个String 长度的话 程序将变得很难解读.

的确的，这应该要借助特殊的函数，咱们现在的知识水平也就只能操作这些语句来做题了，继续学习，共同提高。
作者: skill20    时间: 2014-5-24 18:10
  1. public static void group(){
  2.                 String str = "abc";
  3.                 char[] ch = str.toCharArray();
  4.                 for(int x = 0; x < ch.length; x++){
  5.                         System.out.println(ch[x]);
  6.                         for(int y = 0; y < ch.length; y++){
  7.                                 if(x != y)
  8.                                         System.out.println("" + ch[x] + ch[y]);
  9.                                 for(int z = 0; z < ch.length; z++){
  10.                                         if( x != y && y!= z && x != z)
  11.                                                 System.out.println("" + ch[x] + ch[y]+ ch[z]);
  12.                                 }
  13.                         }
  14.                 }
  15.         }
复制代码
作者: 294645832    时间: 2014-5-24 21:35
e10my 发表于 2014-5-24 17:43
这道题很有意思, 想了好长时间也没有想到思路.最终还是引用了@nash_的一个算法
via : http://blog.csdn.ne ...

我也在网上找到了一个方法，试验了一下  成功了  也有明确的注释，但是没有明白原理   下面附上代码
  1. package com.itheima;


  4. import java.util.Scanner;
  5. import java.util.TreeSet;

  7. public class sssss {
  8.         public static void main(String[] args) {
  9.                 Scanner s = new Scanner(System.in);
  10.                
  11.                 String str = s.next();
  12.                
  13.                 s.close();
  14.                 show(str);
  15.                

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







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