首页 / 算法 / 字符串数组全排列——逐个追加组合算法

字符串数组全排列——逐个追加组合算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了字符串数组全排列——逐个追加组合算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4835字，纯文字阅读大概需要7分钟。

内容图文

我们在笔试面试过程中经常会遇到关于排列与组合的问题，其实这些可以通过递归简单的实现，看下面两个例子：

（1）关于字符串排列的问题

输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

可以这样想：固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac;接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。这样写成递归程序如下：

 

 package com.meession.weekWork;
  import java.util.Scanner;
  public class StringAllConbinations {
　　　　
      public static void permutateSequence(char[] strArrs,int i){
          char temp;
          if(strArrs==null||i>strArrs.length||i<0){
              return;
          }
          else if(i==strArrs.length){
             System.out.println(strArrs);
         }
         else{
             for(int j=i;j<strArrs.length;j++){
                 temp = strArrs[j];//
                 strArrs[j] = strArrs[i];
                 strArrs[i] = temp;
                 permutateSequence(strArrs, i+1);
                 temp = strArrs[j];//
                 strArrs[j] = strArrs[i];
                 strArrs[i] = temp;
             }
         }
     }
     public static voi main(String[] args) {
         Scanner in = new Scanner(System.in);
         String str = in.nextLine();
         char strArrs[] = str.toCharArray();
         permutateSequence(strArrs, 0);
     }
 }

 

 

 

 

（2）关于组合的问题

 

输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中 去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种 选择都很容易用递归实现。

 1 import java.util.ArrayList;  
 2 import java.util.List;  
 3 import java.util.Queue;  
 4 public class Combination {  
 5     public static void combiantion(char chs[]){  
 6         if(chs==null||chs.length==0){  
 7             return ;  
 8         }  
 9         List<Character> list=new ArrayList();  
10         for(int i=1;i<=chs.length;i++){  
11             combine(chs,0,i,list);  
12         }  
13     }  
14     //从字符数组中第begin个字符开始挑选number个字符加入list中  
15     public static void combine(char []cs,int begin,int number,List<Character> list){  
16         if(number==0){  
17             System.out.println(list.toString());  
18             return ;  
19         }  
20         if(begin==cs.length){  
21             return;  
22         }  
23         list.add(cs[begin]);  
24         combine(cs,begin+1,number-1,list);  
25         list.remove((Character)cs[begin]);  
26         combine(cs,begin+1,number,list);  
27     }  
28     public static void main(String args[]){  
29         char chs[]={‘a‘,‘b‘,‘c‘};  
30         combiantion(chs);  
31     }  
32 }

 

输入一个字符串，输出该字符串中所有字母的全排列。程序请适当添加注释。
C++函数原型： void Print（const char *str）
输入样例： abc

分析：

n个字符串的全排列就是n!，而由于2^32=4294967296，12!=479001600，11!=39916800，

本文讨论的算法在限制n<12，关于n>=12的后续讨论。

另外这里输入的字符也是不重复的，重复的相对复杂，后续可以讨论。

 

思想是这样的:比如输入字符串是abc，定义vectorA、vectorB。

先取a放到vectorA中，
然后取b，与进行组合，则有ba，ab，放到vectorB中，同时清空vectorA。
再取c，与vectorB里的ba，ab分别组合。依次得到cba，bca，bac和cab，acb，abc，放到vectorA中。

最后遍历不为空的vector，打印出组合结果。

这个算法就是逐个追加组合算法。

 

代码实现如下：

 

 

[cpp] view plain copy
 
  1. #define MAXNUM 12  
  2.   
  3. //定义2个放结果的vector，交替使用。  
  4. std::vector<char*> g_vecA;  
  5. std::vector<char*> g_vecB;  
  6.   
  7. void Print(const char *str)  
  8. {  
  9.     char Temp;  
  10.     int nLen = strlen(str);  
  11.     char Temp0[2];  
  12.     Temp0[0]=str[0];  
  13.     Temp0[1]=‘\0‘;  
  14.     g_vecA.push_back(Temp0);//先把第一个字母放到容器里  
  15.   
  16.     vector<char*>::iterator itor;  
  17.     for (int i=1; i<nLen; i++)  
  18.     {  
  19.         Temp = str[i];  
  20.   
  21.         if (g_vecA.size()==0)  
  22.         {  
  23.             //遍历B中的元素  
  24.             for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)   
  25.             {  
  26.                 char* p = *itor;  
  27.   
  28.                 int nSize = strlen(p);  
  29.                 //从0到nSize位置放Temp  
  30.                 for (int j=0; j<nSize+1; j++)  
  31.                 {  
  32.                     char* q = new char[nSize+2];//如果放在循环外面则最后都是一个值  
  33.                     for (int k=0; k<j; k++)  
  34.                     {  
  35.                         q[k]=p[k];  
  36.                     }  
  37.   
  38.                     q[j]=Temp;  
  39.   
  40.                     for (int m=j+1; m<nSize+1; m++)  
  41.                     {  
  42.                         q[m]=p[m-1];  
  43.                     }  
  44.   
  45.                     q[nSize+1]=‘\0‘;  
  46.                     g_vecA.push_back(q);  
  47.                 }  
  48.             }  
  49.   
  50.             for (itor = g_vecB.end()-1; itor>=g_vecB.begin(); itor--)  
  51.             {  
  52.                 char* p = *itor;  
  53.                 g_vecB.erase(itor);  
  54.             }  
  55.             g_vecB.clear();  
  56.         }  
  57.         else  
  58.         {  
  59.             //遍历A中的元素  
  60.             for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)   
  61.             {  
  62.                 char* p = *itor;  
  63.                   
  64.                 int nSize = strlen(p);  
  65.                   
  66.                 //从0到nSize位置放Temp  
  67.                 for (int j=0; j<nSize+1; j++)  
  68.                 {  
  69.                     char* q = new char[nSize+2];  
  70.                     for (int k=0; k<j; k++)  
  71.                     {  
  72.                         q[k]=p[k];  
  73.                     }  
  74.                       
  75.                     q[j]=Temp;  
  76.                       
  77.                     for (int m=j+1; m<nSize+1; m++)  
  78.                     {  
  79.                         q[m]=p[m-1];  
  80.                     }  
  81.                     q[nSize+1]=‘\0‘;  
  82.                     g_vecB.push_back(q);  
  83.                 }  
  84.             }  
  85.   
  86.             for (itor = g_vecA.end()-1; itor>=g_vecA.begin(); itor--)  
  87.             {  
  88.                 char* p = *itor;  
  89.                 g_vecA.erase(itor);  
  90.             }  
  91.             g_vecA.clear();  
  92.         }  
  93.     }  
  94.   
  95.     int nCount = 0;  
  96.   
  97.     //打印所有组合  
  98.     if (g_vecA.size()==0)  
  99.     {  
  100.         for(itor=g_vecB.begin();itor!=g_vecB.end();itor++)   
  101.         {  
  102.             nCount ++;  
  103.             char* p = *itor;  
  104.             cout << p << ", ";  
  105.   
  106.             if (nCount%10 == 0)  
  107.             {  
  108.                 cout << endl;  
  109.             }  
  110.   
  111.             delete p;  
  112.             p=NULL;  
  113.         }  
  114.     }  
  115.     else  
  116.     {  
  117.         for(itor=g_vecA.begin();itor!=g_vecA.end();itor++)   
  118.         {  
  119.             nCount ++;  
  120.             char* p = *itor;  
  121.             cout << p << ", ";  
  122.               
  123.             if (nCount%10 == 0)  
  124.             {  
  125.                 cout << endl;  
  126.             }  
  127.   
  128.             delete p;  
  129.             p=NULL;  
  130.         }  
  131.     }  
  132.   
  133.     g_vecA.clear();  
  134.     g_vecB.clear();  
  135.   
  136.     cout << endl;  
  137.   
  138. }  

 

[cpp] view plain copy
 
  1. int main()    
  2. {     
  3.     g_vecA.clear();  
  4.     g_vecB.clear();  
  5.     char str[MAXNUM];  
  6.   
  7.     char Temp[256];  
  8.     scanf("%s", Temp);  
  9.   
  10.     if (strlen(Temp)>=12)  
  11.     {  
  12.         cout<<"字符串长度是1-11。" <<endl;  
  13.   
  14.         return 0;  
  15.     }  
  16.     else  
  17.     {  
  18.         strcpy(str, Temp);  
  19.     }  
  20.   
  21.     Print(str);  
  22.   
  23.     return 0;    
  24. }    

 

 

测试结果：

当输入abc时：

cba, bca, bac, cab, acb, abc,

当输入abcd时：

dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac,
badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd,
dabc, adbc, abdc, abcd,

 

原文：http://www.cnblogs.com/qiaoyanlin/p/6878405.html

内容总结

以上是互联网集市为您收集整理的字符串数组全排列——逐个追加组合算法全部内容，希望文章能够帮你解决字符串数组全排列——逐个追加组合算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1108632.html

来源：【匿名】