字符串的全排列详解，递归+非递归_字符串abc 排序

1. 首先，我们固定第一个字符a，求后面两个字符bc的排列
2. 当两个字符bc排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列
3. 现在是把c放在第一个位置的时候了，但是记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍是和原先处在第一个位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处于第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列
4. 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了

#include"stdafx.h"
#include"iostream"
#include <string.h>
using namespace std;
   
 
int count;  //统计全排列的个数
   
void swap(char *str, int a, int b)  
{  
    char temp;  
    temp = str[a];  
    str[a] = str[b];  
    str[b] = temp;  
}  
   
void permutation_process(char *str, int begin, int end) {  
    int k;  
   
    if (begin == end - 1) {  
        cout<<"第"<<count++<<"个全排列"<<str<<endl;
<span style="white-space:pre">	</span>}else {  
        for (k = begin; k < end; k ++) {  
            swap(str, k, begin);  
            permutation_process(str, begin + 1, end);  
            swap(str, k, begin);  
        }  
    }  
}  
   
int _tmain(int argc, _TCHAR* argv[])
{
<span style="white-space:pre">	</span>char str[7];  
<span style="white-space:pre">	</span>int i, len;  
<span style="white-space:pre">	</span>cin>>str;
<span style="white-space:pre">	</span>count = 1;  
        len = strlen(str);  
        permutation_process(str, 0, len);  
          
    return 0;  
}  

2、去掉重复的全排列的递归实现

#include "stdafx.h"
#include"iostream"
#include <string.h>
using namespace std;   
int count;  //统计全排列的个数
  
void swap(char *str, int a, int b)  
{  
    char temp;  
    temp = str[a];  
    str[a] = str[b];  
    str[b] = temp;  
}  
 
int is_swap(char *str, int begin, int k)  
{  
    int i, flag;  
      for (i = begin, flag = 1; i < k; i ++) {  
        if (str[i] == str[k]) {  
            flag = 0;  
            break;  
        }  
    }    
    return flag;  
}  
   
void permutation_process(char *str, int begin, int end) {  
    int k;  
     if (begin == end - 1) {  
          cout<<"第"<<count++<<"个全排列"<<str<<endl;
	}else {  
       <span style="white-space:pre">	</span>	for (k = begin; k < end; k ++) {  
          <span style="white-space:pre">	</span>  if(is_swap(str,  begin, k) ){
<span style="white-space:pre">			</span>swap(str, k, begin);  
           <span style="white-space:pre">		</span>permutation_process(str, begin + 1, end);  
          <span style="white-space:pre">		</span>swap(str, k, begin);  
		  }
		}
  <span style="white-space:pre">	</span>  }  
    }  
   
 
int _tmain(int argc, _TCHAR* argv[])
{
    int i, len;  
    cin>>str;
    count = 1;  
    len = strlen(str);  
    permutation_process(str, 0, len);  
    return 0;  
}  

3、全排列非递归实现

思路

//全排列非递归
#include"stdafx.h"
#include<iostream>  
#include<algorithm>  
#include<cstring>  
using namespace std;  
#include<assert.h>  
  
//反转区间  
void Reverse(char* pBegin , char* pEnd)  
{  
    while(pBegin < pEnd)  
        swap(*pBegin++ , *pEnd--);  
}  
//下一个排列  
bool Next_permutation(char a[])  
{  
    assert(a);  
    char *p , *q , *pFind;  
    char *pEnd = a + strlen(a) - 1;  
    if(a == pEnd)  
        return false;  
    p = pEnd;  
    while(p != a)  
    {  
        q = p;  
        p--;  
        if(*p < *q)  //找降序的相邻2数,前一个数即替换数    
        {  
             //从后向前找比替换点大的第一个数  
            pFind = pEnd;  
            while(*pFind < *p)  
                --pFind;  
            swap(*p , *pFind);  
            //替换点后的数全部反转  
            Reverse(q , pEnd);  
            return true;  
        }  
    }  
    Reverse(a , pEnd);   //如果没有下一个排列,全部反转后返回false     
    return false;  
}  
  
int cmp(const void *a,const void *b)  
{  
    return int(*(char *)a - *(char *)b);  
}  
int main(void)  
{  
    char str[] = "bac";  
    int num = 1;  
    qsort(str , strlen(str),sizeof(char),cmp);  
    do  
    {  
        printf("第%d个排列\t%s\n",num++,str);   
    }while(Next_permutation(str));  
    return 0;  
}