首页 > 代码库 > 字符串数组全排列——逐个追加组合算法

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

2024-09-23 10:16:02   217人阅读

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

（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,

 

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


联系
我们