字符串排列，for循环嵌套递归

朱雀 2022-06-08 01:27 207阅读 0赞

字符串的排列，就是给定一个字符串，输出能排列出的所有的字符串，如给定abc的排列有：abc，acb，bac,bca,cba,cab,写这个算法主要是想练习for循环中嵌套递归是怎么执行的，其实单纯的递归算法还是相对好理解的，你想找一个问题的递归算法，就是先把问题分成更小的子问题，并且这个分割还要是有限的，得有终止递归的条件，然后就是用什么方法解决最小的问题。

算法写出来后，验证算法的正确性，运行下最直观，也可以通过读代码来判断，先判断终止条件时的结果是不是正确，通常是等与0,1时，然后就是如果对于n正确，那么对于n-1也应该正确。

这个字符串的排列算法，思路就是固定一个位置，然后跟其余的字符逐个交换，其中要考虑字符中有重复的字符的情况。

#include <iostream>
    
    using namespace std;
    
    bool doSwap(char* pBegin,char* pCh){
    	//不能改变pBegin的指向
    	char* pTemp;
    	for(pTemp = pBegin;pTemp < pCh;pTemp++){
    		if(*pTemp == *pCh)
    			return false;
    	}
    	return true;
    }
    
    void permutation(char* pStr,char* pBegin){
    	static int pmt =0;
    	static int num =1;
    	cout <<"第- "<<num <<" -层循环,,"<<"第- "<<pmt++<<" -次递归"<<endl;
    	if(*pBegin == '\0'){	
    		pmt =1;	
    		cout <<"第 "<< num++<<"个 排列："<<pStr<<endl;
    	}else{
    		int index =1;
    		for(char* pCh = pBegin; *pCh !='\0'; pCh++,index++){
    			//是否做交换，取决于pCh是否跟pBegin ~ pCh之间的数有重复，当然不包含pCh自己跟自己比较
    			if(doSwap(pBegin,pCh)){
    				cout<<"第index= "<<index<<" 次循环，" <<"befor swap,*pStr="<<*pStr<<",,pch="<<*pCh<<",,pBegin="<<*pBegin<<endl;
    				char temp = *pCh;
    				*pCh = *pBegin;
    				*pBegin = temp;
    				cout<<"第index= "<<index<<" 次循环,当前pStr="<<pStr<<" ,after swap,pCh="<<*pCh<<",,pBegin="<<*pBegin<<endl;
    				permutation(pStr,pBegin+1);
    				cout<<"第index= "<<index<<" 次循环,当前pStr="<<pStr<<" ,递归返回,pCh="<<*pCh<<",,pBegin="<<*pBegin<<endl;
    				//每次递归返回后，把前面交换的数值在换回去，
    				temp = *pCh;
    				*pCh = *pBegin;
    				*pBegin = temp;
    				cout<<"第index= "<<index<<" 次循环,还原后 pStr="<<pStr<<endl;
    			}	
    		}
    
    	}
    
    }
    
    int main(int argc, char* argv[]){
    	char str[] = "abc";
    	permutation(str,str);
    	return 0;
    }

测试结果：

先粘贴一个排列少的ab：

PC:~/algorithm$ ./StringPermutation  
第- 1 -层循环,,第- 0 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=ab ,after swap,pCh=a,,pBegin=a  
第- 1 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=ab ,after swap,pCh=b,,pBegin=b  
第- 1 -层循环,,第- 2 -次递归  
第 1个 排列：ab  
第index= 1 次循环,当前pStr=ab ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=ab  
第index= 1 次循环,当前pStr=ab ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=ab  
第index= 2 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=a  
第index= 2 次循环,当前pStr=ba ,after swap,pCh=a,,pBegin=b  
第- 2 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=ba ,after swap,pCh=a,,pBegin=a  
第- 2 -层循环,,第- 2 -次递归  
第 2个 排列：ba  
第index= 1 次循环,当前pStr=ba ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=ba  
第index= 2 次循环,当前pStr=ba ,递归返回,pCh=a,,pBegin=b  
第index= 2 次循环,还原后 pStr=ab

下面是字符串abb的排列：

PC:~/algorithm$ ./StringPermutation  
第- 1 -层循环,,第- 0 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=abb ,after swap,pCh=a,,pBegin=a  
第- 1 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=abb ,after swap,pCh=b,,pBegin=b  
第- 1 -层循环,,第- 2 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=abb ,after swap,pCh=b,,pBegin=b  
第- 1 -层循环,,第- 3 -次递归  
第 1个 排列：abb  
第index= 1 次循环,当前pStr=abb ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=abb  
第index= 1 次循环,当前pStr=abb ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=abb  
第index= 1 次循环,当前pStr=abb ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=abb  
第index= 2 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=a  
第index= 2 次循环,当前pStr=bab ,after swap,pCh=a,,pBegin=b  
第- 2 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=bab ,after swap,pCh=a,,pBegin=a  
第- 2 -层循环,,第- 2 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=bab ,after swap,pCh=b,,pBegin=b  
第- 2 -层循环,,第- 3 -次递归  
第 2个 排列：bab  
第index= 1 次循环,当前pStr=bab ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=bab  
第index= 1 次循环,当前pStr=bab ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=bab  
第index= 2 次循环，befor swap,\*pStr=b,,pch=b,,pBegin=a  
第index= 2 次循环,当前pStr=bba ,after swap,pCh=a,,pBegin=b  
第- 3 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=bba ,after swap,pCh=a,,pBegin=a  
第- 3 -层循环,,第- 2 -次递归  
第 3个 排列：bba  
第index= 1 次循环,当前pStr=bba ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=bba  
第index= 2 次循环,当前pStr=bba ,递归返回,pCh=a,,pBegin=b  
第index= 2 次循环,还原后 pStr=bab  
第index= 2 次循环,当前pStr=bab ,递归返回,pCh=a,,pBegin=b  
第index= 2 次循环,还原后 pStr=abb

字符串是abc的排列：

PC:~/algorithm$ g++ StringPermutation.cpp -o StringPermutation  
PC:~/algorithm$ ./StringPermutation  
第- 1 -层循环,,第- 0 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=abc ,after swap,pCh=a,,pBegin=a  
第- 1 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=abc ,after swap,pCh=b,,pBegin=b  
第- 1 -层循环,,第- 2 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=c,,pBegin=c  
第index= 1 次循环,当前pStr=abc ,after swap,pCh=c,,pBegin=c  
第- 1 -层循环,,第- 3 -次递归  
第 1个 排列：abc  
第index= 1 次循环,当前pStr=abc ,递归返回,pCh=c,,pBegin=c  
第index= 1 次循环,还原后 pStr=abc  
第index= 1 次循环,当前pStr=abc ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=abc  
第index= 2 次循环，befor swap,\*pStr=a,,pch=c,,pBegin=b  
第index= 2 次循环,当前pStr=acb ,after swap,pCh=b,,pBegin=c  
第- 2 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=acb ,after swap,pCh=b,,pBegin=b  
第- 2 -层循环,,第- 2 -次递归  
第 2个 排列：acb  
第index= 1 次循环,当前pStr=acb ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=acb  
第index= 2 次循环,当前pStr=acb ,递归返回,pCh=b,,pBegin=c  
第index= 2 次循环,还原后 pStr=abc  
第index= 1 次循环,当前pStr=abc ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=abc  
第index= 2 次循环，befor swap,\*pStr=a,,pch=b,,pBegin=a  
第index= 2 次循环,当前pStr=bac ,after swap,pCh=a,,pBegin=b  
第- 3 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=bac ,after swap,pCh=a,,pBegin=a  
第- 3 -层循环,,第- 2 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=c,,pBegin=c  
第index= 1 次循环,当前pStr=bac ,after swap,pCh=c,,pBegin=c  
第- 3 -层循环,,第- 3 -次递归  
第 3个 排列：bac  
第index= 1 次循环,当前pStr=bac ,递归返回,pCh=c,,pBegin=c  
第index= 1 次循环,还原后 pStr=bac  
第index= 1 次循环,当前pStr=bac ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=bac  
第index= 2 次循环，befor swap,\*pStr=b,,pch=c,,pBegin=a  
第index= 2 次循环,当前pStr=bca ,after swap,pCh=a,,pBegin=c  
第- 4 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=b,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=bca ,after swap,pCh=a,,pBegin=a  
第- 4 -层循环,,第- 2 -次递归  
第 4个 排列：bca  
第index= 1 次循环,当前pStr=bca ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=bca  
第index= 2 次循环,当前pStr=bca ,递归返回,pCh=a,,pBegin=c  
第index= 2 次循环,还原后 pStr=bac  
第index= 2 次循环,当前pStr=bac ,递归返回,pCh=a,,pBegin=b  
第index= 2 次循环,还原后 pStr=abc  
第index= 3 次循环，befor swap,\*pStr=a,,pch=c,,pBegin=a  
第index= 3 次循环,当前pStr=cba ,after swap,pCh=a,,pBegin=c  
第- 5 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=c,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=cba ,after swap,pCh=b,,pBegin=b  
第- 5 -层循环,,第- 2 -次递归  
第index= 1 次循环，befor swap,\*pStr=c,,pch=a,,pBegin=a  
第index= 1 次循环,当前pStr=cba ,after swap,pCh=a,,pBegin=a  
第- 5 -层循环,,第- 3 -次递归  
第 5个 排列：cba  
第index= 1 次循环,当前pStr=cba ,递归返回,pCh=a,,pBegin=a  
第index= 1 次循环,还原后 pStr=cba  
第index= 1 次循环,当前pStr=cba ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=cba  
第index= 2 次循环，befor swap,\*pStr=c,,pch=a,,pBegin=b  
第index= 2 次循环,当前pStr=cab ,after swap,pCh=b,,pBegin=a  
第- 6 -层循环,,第- 1 -次递归  
第index= 1 次循环，befor swap,\*pStr=c,,pch=b,,pBegin=b  
第index= 1 次循环,当前pStr=cab ,after swap,pCh=b,,pBegin=b  
第- 6 -层循环,,第- 2 -次递归  
第 6个 排列：cab  
第index= 1 次循环,当前pStr=cab ,递归返回,pCh=b,,pBegin=b  
第index= 1 次循环,还原后 pStr=cab  
第index= 2 次循环,当前pStr=cab ,递归返回,pCh=b,,pBegin=a  
第index= 2 次循环,还原后 pStr=cba  
第index= 3 次循环,当前pStr=cba ,递归返回,pCh=a,,pBegin=c  
第index= 3 次循环,还原后 pStr=abc