字典序:生成下一个排列

字典序:生成下一个排列

用字典序生成排列,一个排列若按字典序,可以设计如下的树,例如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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注