字典序：生成下一个排列
用字典序生成排列，一个排列若按字典序，可以设计如下的树，例如N=4，根结点有4个子树，按顺序将这四个树的结点值排好。每个子树又有3个子树，其结点的值是父结点所不含有的那些值。直到将N层建好，则依次就是字典序的排列。
按照字典序的规则，已知一个N的排列 \( p_1,p_2,…p_N \)，求下一个排列的算法如下描述：
STEP 1. 求符合 \( p_{j-1} < p_j \) 的j的最大值，记为i
STEP 2. 求符合 \( p_{i-1}<p_k \)的k的最大值，记为h
STEP 3. \( p_{i-1} \)与 \( p_{h} \)互换
STEP 4. 将互换后序列的\(p_i\)到\(p_N\)逆转，便得到下一个序列。
以N=4，序列\( (3,4,2,1) \)为例， \( p_{j-1} < p_j \) 的最大值为i=2， \( p_1<p_k \) 的k的最大值h=2。将p[1]与p[2]互换，并将p[2]到p[4]逆序，则得 \( (4,1,2,3) \)
若要生成N的全排列，可以从 \( (1,2,…,N) \) 开始，反复使用求下一个排列的方法，直到不存在 \( p_{j-1} < p_{j} \) 为止
#include <cstdio>
#include <cstring>
#define MAXN 30
void swap(char *s,int x,int y)
{
char tmp = s[x];
s[x] = s[y];
s[y] = tmp;
}
void reverse(char *s,int lwbd,int upbd)
{
int i;
for(i=0;i<(upbd-lwbd)/2;i++)
{
swap(s,lwbd+i,upbd-i);
}
}
int next_arrange(char* p,int N)
{
int k,i=-1,h;
for(k=N;k>1;k--)
{
if(p[k-1]<p[k])
{
i=k;
break;
}
}
if(i==-1)
return 0;
for(k=N;k>1;k--)
{
if(p[i-1]<p[k])
{
h=k;
break;
}
}
swap(p,i-1,h);
reverse(p,i,N);
return 1;
}
int main(void)
{
int i,h,k,N;
char p[MAXN];
scanf("%d",&N);
for(k=1;k<=N;k++)
{
p[k]=k;
}
while(1)
{
int status = next_arrange(p,N);
if(status==0)
break;
for(k=1;p[k];k++)
{
printf("%d",p[k]);
}
printf("\n");
}
return 0;
}