黑马程序员技术交流社区

标题: 一道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.         }

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

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

  70.         }

  71. }
复制代码

这道题很有意思, 想了好长时间也没有想到思路.最终还是引用了@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;


  2. import java.util.Scanner;
  3. import java.util.TreeSet;

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

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








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