LexicographicPermute(求字典序的下一个字典序)

伪代码

算法 LexicographicPermute(n)

//以字典序产生排列

//输入：一个正整数n

//输出：在字典序下{1,……，n}所有排列的列表

初始化第一个排列为12……n

While 最后一个排列有两个连续升序的元素 do

找到使得ai<ai+1的最大的i     //ai+1>ai+2>ai+3>……>an

找到使得ai<aj的最大索引j    //j>=i+1,因为ai<ai+1

交换ai和aj   //ai+1ai+2……an任保持降序

将ai+1到an的元素反序

将这个新排列添加到列表中

//14世纪印度时的某个算法，感叹啊，那个时候的人就这么聪明了
//此方法可以用来求字典序的下一个序列
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
void LexicographicPermute(int *a,int n)
{
    //开始时数组a[0,1,2,3，……,n-1]的序列时为1,2,3,4,5……n
    int k=n-2,j;
    for(int i=0; i<n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
    while(1)
    {
        for(j=n-1; j>k; j--)
        {
            if(a[j]>a[k])
            {
                swap(a[j],a[k]);
                break;
            }
        }
        for(int i=k+1; i<n-i+k; i++)
            swap(a[i],a[n-i+k]);
        for(k=n-1; k>0; k--)
            if(a[k]>a[k-1])
                break;
        for(int i=0; i<n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
        if(k--==0) break;
    }
}
int main()
{
    int a[1000],n;
    cin>>n;
    for(int i=0; i<n; i++)
        a[i]=i+1;
    LexicographicPermute(a,n);
    return 0;
}