C++递归与非递归实现全排列

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

参考文章：http://blog.csdn.net/morewindows/article/details/7370155

http://plutoblog.iteye.com/blog/976216，离散数学及其运用P137

什么是按字典顺序排序的生成排列？

如果在n个正整数集合的两个排列不等的第一个位置，如果一个排列的数小于第二个排列的数，那么这个排列按照字典顺序排在第二个排列的前面

如果要实现按字典顺序生成排列，那么请使用非递归的方法。

//premutation(排列)
//如果要求字典序就用非递归的方法或者直接使用STL中的next_permutation()函数。
//本递归的方法无法实现排列按字典顺序出现
#include "quicksort.h"
int flag=1;//标志位，标记这是第几个


//****************************************************全排列的递归实现
void swap(int *p1,int *p2)
{
int temp=*p1;
*p1=*p2;
*p2=temp;
}
//必须有这个，要排除掉那些重复的排列，去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换，
//也就是只有第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数才交换
bool Isswap(int* num,int start,int end) // start==end或者是start到end没有等于num[end]的值得这两种情况都是可以进行交换的
{
for(int i=start;i<end;i++)
if(num[i]==num[end])
return false;
return true;
}
void allrange(int* num,int k,int m)//全排列的核心思想
{
if(k>m)
cout<<"wrong input"<<endl;
if(k==m)
{
cout<<"第"<<flag<<"个排列";//注意flag标志位必须定义为一个全局变量，不能定义在allrange函数中，否则每次递归flag又从新定义为1了，每次都没有变化
flag++;
for(int i=0;i<=m;i++)//注意数组的输出只能够一次遍历其每一个值
cout<<num[i];
cout<<endl;
}
else
{
for(int i=k;i<=m;i++)
{
if(Isswap(num,k,i))
{
//swap(num+k,num+i);//注意不能够写为swap(num[k],num[i]),要么写成swap(num+k,num+i)
swap(&num[k],&num[i]);
allrange(num,k+1,m);
swap(num+k,num+i);
}
}
}
}


//********************************************************************全排列的非递归实现
//在求字符串的全排列的时候，首先要对字符串进行排序，使得其按升序排序，因为求全排列的算法是按照降序排序的
//这里用快速排序首先处理字符串
void reverse(int *a,int *b)//反转
{
while(a<b)   //这里a，b都是地址，不是值，比如2660，反转后为0662，因为在一开始进行了快排使得序列按照从小到大的顺序排列（升序），
swap(a++,b--);//因为在进行全排列时进行了判断，所以肯定在a到b这段范围内的值都是满足从大到小的顺序，反转后就满足从小到大的顺序，这是生成排列的构造规则
}
bool next_permutation(int num[],int length)
{
//如果不传递length写为length=sizeof(num)/sizeof(int)，则实际中求出sizeof(num)为0，因为num是函数的参数。
int *pend=num+length;//超过了位数，比如num有9个，num+9实际是从0到9有十个，所以后面用pend初始化p时要减去1
if(num==pend)
return false;
pend--;
int *p,*q,*pfind;
p=pend;
while(p!=num)
{
q=p;
--p;
if(*p<*q)//生成排列的构造规则，找到降序排列的相邻两个数，前一个数就是要替换掉的数
{
pfind=pend;
while(*pfind<=*p)
--pfind;      //找到第一个大于*p的数，它就是*p之后刚好大于*p的最小的那个数，用它来替换之前找到的那个要替换的数
swap(pfind,p);
//替换后，把q到end的数全部反转，使它们是从小到大排序
reverse(q,pend);
return true;
}
}
reverse(p,pend);//表明此时已经是最大序列了，形如4321，将字符串整个颠倒过来得到最小的排列，并返回false
return false;
}




int main()
{
int num[]={1,3,2,4};
int length=sizeof(num)/sizeof(int);
//allrange(num,0,length-1);
quicksort(num,length,0,length-1);
int k=1;
do{
cout<<"第"<<k++<<"个排列是"<<":";
for(int i=0;i<length;i++)
cout<<num[i]<<" ";
cout<<endl;
}while(next_permutation(num,length));
return 0;
}