全排列_字典序排列.cpp

/*
一、问题：全排列（此方法适合有序的排列，因为它每次是找下一个排列，所以可以先排序再用此方法 ） 
 
二、字典序
根据维基百科的定义：给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔集 A × B，则字典序定义为
(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′)。
所以给定两个字符串，逐个字符比较，那么先出现较小字符的那个串字典顺序小，如果字符一直相等，较短的串字典顺序小。
例如：abc < abcd < abde < afab。

三、偏序集
一个集合A与A上的偏序关系R一起叫作偏序集，记作<A,R>或<A, ≦>。
（自反性）对任一  ，则x≦x;
（反对称性）如果x≦y,且y≦x,则x=y;
（传递性）如果x≦y,且y≦c ,则x≦c. 

四、说明：1、假定现有字符串(A)x(B)，它的下一个排列是：(A)y(B’)，其中A、B和B’是“字符串”(可能为空），x和y是“字符”，前缀相同，都是A，且一定有y > x。
	  2、那么，为使下一个排列字典顺序尽可能小，必有：
		（1）A尽可能长
		（2）y尽可能小
		（3）B’里的字符按由小到大递增排列 
比如说，现在我们要找21543的下一个排列，我们可以从左至右逐个扫描每个数，看哪个能增大
（至于如何判定能增大，是根据如果一个数右面有比它大的数存在，那么这个数就能增大），
我们可以看到最后一个能增大的数是：x = 1。
而1应该增大到多少？1能增大到它右面比它大的那一系列数中最小的那个数，
即：y = 3，故此时21543的下一个排列应该变为23xxx，显然 xxx(对应之前的B’）应由小到大排，
于是我们最终找到比“21543”大，但字典顺序尽量小的23145，找到的23145刚好比21543大。

五、步骤（二找、一交换、一翻转）

1、找到排列中最后（最右）一个升序的首位位置i，x = ai
2、找到排列中第i位右边最后一个比ai 大的位置j，y = aj
3、交换x，y
4、把第(i+ 1)位到最后的部分翻转


*/
#include <iostream>
using namespace std;

//交换 
void swap(char *a,char *b)
{
	char temp=*a;
	*a=*b;
	*b=temp;
}
//翻转 
void reverse(char *s,int i,int j)
{
	while(i<j){
		swap(s+i,s+j);	
		++i;
		--j;
	}
		
}
//全排列并判断是否结束 
bool allPermutation(char *s,int len)
{
	int i,k;
	for(i=len-2;(i>=0) && (s[i]>=s[i+1]);--i);//从后向前找到第一个升序的位置 
	
	if(i<0)//所有的都已经找到，则返回false 
		return false;
	
	for(k=len-1;(k>i) && (s[k]<=s[i]);--k);//从后向前找到第一个比i位置大的数 
	
	swap(s+i,s+k);//交换两位置的数 
	reverse(s,i+1,len-1);//将i位置后面的数逆序 
	return true;
} 

int main()
{
	//输入 
	cout<<"请输入字符串（以0结尾）："<<endl;
	char *s,data;
	int n=0,i,count=1;
	while(cin>>data && data!='0'){
		s[n++]=data;
	} 
	//结果
	cout<<count<<":"<<s<<endl;
	while(allPermutation(s,n)){//判断是否结束排序 
		cout<<(++count)<<":"<<s<<endl;//输出得到的排列 
	}
	return 0;
}