字符串全排列——重复和非重复

刺骨的言语ヽ痛彻心扉 2022-08-05 17:30 157阅读 0赞

**字符串全排列——重复和非重复**

# 1. 题目 #

输入一个字符串，打印出该字符串中字符的所有排列。例如：输入abc, 我们就可以得到abc, acb, bac, bca, cab, cba。

这个题目主要有两种思路：递归和非递归。下面我们逐一解释。

# 2. 递归方法 #

基本原理我们用下图来展示：

![Center][]

> 首先，让每个字符都当一次head，把第一个字符和后面的字符一一交换；

> 然后，固定第一个字符，（见上图黑框），求后面字符的全排列（递归思想），也就是继续把后面的字符分成两部分，第一个字符和后面的字符逐一交换。
> 
> （注意，递归跳出的条件是字符串的head指针指向末尾！）
> 
>   
>

实现代码如下：

#include<iostream>
    
    using namespace std; 
    
    void Permutation(char *str, char *head)
    {
    	if(str==NULL)
    		return; 
    
    	if(*head=='\0')  //head指针扫到结尾了
    		cout<<str<<endl; 
    	else
    	{
    		for(char *p=head; *p!='\0'; p++)
    		{
    			swap(*p, *head);  //交换头指针指向的字符
    			Permutation(str, head+1); 
    			swap(*p,*head);  //交换回来
    		}
    	}
    }
    
    int main()
    {
    	char str[10]; 
    	cout<<"The original string is: "; 
    	cin>>str; 
    	cout<<endl; 
    	cout<<"After permutation, the string is: "<<endl;
    	Permutation(str, str); 
    
    	return 0; 
    }

**注意递归算法一定要想好跳出递归的条件！**

# 3. 非递归方法——字典序排列 #

上面的递归算法简单异想，但是很多时候，我们需要非递归算法提升高效性。

这种问题类似于我们查找英文字典一样，我们需要从当前排列生成字典序刚好比它大的下一个排列。而我们的起点是字典序最小的排列，终点是字典序最大的排列。到时候我们直接输出即可。

例如：现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），我们可以看到最后一个能增大的数是：x = 1。而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

（https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.06.md）

算法步骤如下：

Step 1：找到排列中最右边一个升序的首位位置i;

Step 2：找到排列中第i位右边最后一个比str\[ i \]大的位置j；

Step 3：交换str\[ i \]和str\[ j \]；

Step 4：把第i+1位到最后的部分翻转。

上面这个功能在STL中已经集中为next\_permutation()函数，我们可以直接调用，也可以自己写一下。

代码如下：

直接调用next\_permutation版本：（需要加上algorithm头文件）

#include<iostream>
    #include<algorithm>
    using namespace std; 
    
    void Permutation(char *str)
    {
    	int len=strlen(str); 
    	sort(str, str+len); 
    	do
    	{
    		cout<<str<<endl; 
    	}while(next_permutation(str, str+len)); 
    }
    
    int main()
    {
    	char str[10]; 
    	cout<<"The original string is: "; 
    	cin>>str; 
    	cout<<endl; 
    	cout<<"After permutation, the string is: "<<endl;
    	Permutation(str); 
    
    	return 0; 
    }

自己写next\_permutation版本，参考（上面的链接）：

bool CalcAllPermutation(char* perm, int num){
        int i;
    
        //①找到排列中最后（最右）一个升序的首位位置i，x = ai
        for (i = num - 2; (i >= 0) && (perm[i] >= perm[i + 1]); --i){
            ;
        }
        // 已经找到所有排列
        if (i < 0){
            return false;
        }
    
        int k;
        //②找到排列中第i位右边最后一个比ai 大的位置j，y = aj
        for (k = num - 1; (k > i) && (perm[k] <= perm[i]); --k){
            ;
        }
    
        //③交换x，y
        swap(perm[i], perm[k]);
        //④把第(i+ 1)位到最后的部分翻转
        reverse(perm + i + 1, perm + num);
        return true;
    }

至此，字符串的全排列就说好了。

但是有个问题，上面题目中输入的字符串都没有重复字符，如果有呢？

# 4. 存在重复字符的全排列 #

首先，next\_permutation可以直接用来处理这种情况，上面的代码不变！

然后，递归的方式，去重的全排列就是从第一个字符开始，每个字符分别与它后面非重复出现的字符交换。即在程序中，每次交换的时候我们都需要判断一下，交换两个字符中间，是否有与被交换字符重复。

代码如下，参考：（http://blog.csdn.net/zhaojinjia/article/details/9320475）

//在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等    
    bool IsSwap(char* pBegin, char* pEnd)    //这部分是重点！！
    {  
        char* p;  
        for (p=pBegin; p<pEnd; p++)  
        {  
            if (*p == *pEnd)  
                return false;  
        }  
        return true;  
    }  
      
    void Permutation(char* pStr, char* pBegin)  
    {  
        if (*pBegin == '\0')  
            cout << pStr <<endl;  
        else  
        {  
            for (char* pCh = pBegin; *pCh!='\0'; pCh++)  
            {  
                if( IsSwap(pBegin,pCh) )  
                {  
                    char temp = *pCh;    
                    *pCh = *pBegin;    
                    *pBegin = temp;    
      
                    Permutation(pStr, pBegin+1);    
      
                    temp = *pCh;    
                    *pCh = *pBegin;    
                    *pBegin = temp;    
                }  
            }  
        }  
    }

[Center]: /images/20220806/a1a3e9317506450da097af1cb7bc1e5b.png