问题描述

n个元素{1,2，…,n}有n!个不同的排列。将这n!个排列按字
典序排列，并编号为0,1，…,n!-1.每个排列的编号为其字典序值。例如，当
n=3时，6个不同排列的字典序值如下：

算法设计

给定n及n个元素{1,2，…,n}的一个排列，计算出这个排列的字典
序值，以及按字典排列的下一个排列。

数据输入和数据输出

• 数据输入：第1行是元素个数n。接下来的1行是n个元素{1,2，…,n}的一个排列。

• 结果输出：第一行是字典序值，第2行是按字典序排列的下一个排列，如果不存在则输出-1

          输入文件示例                输出文件示例 
         8                              8227
         2 6 4 5 8 1 7 3            2 6 4 5 8 3 1 7
  

算法分析

整个求解过程分为两个部分，第一部分求解字典序值，第二部分求解新的排列序列，求解思路如下：

求解字典序值

求解字典序值，有两种实现方法，可以用递归和非递归实现：
（1）非递归实现
首先给定一个序列，我们想要求解这个序列的字典序数，我们可以依次处理某一个标号位置，比他小的序号数肯定可以排列出合法的序列，假设这个位置的标号为i，其后比他小的数的个数是j，那么可以排列出比这个序列小的序列数是(n-i-1)!*j,列举每一个位置，则可以得到字典序值为∑<0,n-1>((n-i-1)!*j).,算法步骤如下：

• for循环一次枚举每一个下标
• 统计这序列后小于这个数的个数
• 计算阶乘
• 求和

（2）递归实现

递归实现代码：

int perRank(int *pi,int n)
{
    for (int j=1,r=0;j<=n;j++)
    rho[j]=pi[j];
    for(j=1;j<=n;j++)
    {
        r+=(rho[j]-1)*perm(n-j);
        for(int i=j+1;i<=n;i++)
            if(rho[i]>rho[j])
                rho[i]--;
    }
    return r;
}

求解新的排列

对于一个序列，我们如何求解新的排列呢？枚举出所有的序列？那太大动干戈了，我们有更聪明的算法：
不妨这样考虑，对于一个递减的序列，我们还有办法给出下一个序列吗？当然不可以，那么我们的关键也就是递减序列，这个序列之前，必须要存在比递减序列的第一个数要小的数才能给出正确的下一序列。我们假设有list[i]<list[i+1]，并且list[i+1]>list[i+2]....list[n-1],那么我们将list[i]和递减序列中的哪个数据交换呢？我们知道这个递减序列中存在比list[i]要大的序列S，我们要将S中最小的这个数和list[i]交换，这样才能使得新的序列最小，如下图所示：

现在我们给出算法步骤：

• 对于给定的排列L,首先找到下标i，使得L[i]<L[i+1],且L[i+1]>L[i+2]>…>L[n]
• 其次找到下标j,使得L[i]<L[j]且对所有j<k≤n有L[k]≤L[j]
• 然后交换L[i]和L[j]
• 最后将子排列L[i+1], L[i+2], … L[n]反转

代码实现

#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
int maxn=100;
LL perm(int n)
{
    if(n==1) return 1;
    return n*perm(n-1);
}
LL order(int list[],int n)
{
    LL sum=0;
    int num;
    for(int i=0;i<n-1;i++)
    {
        num=0;
        //统计比list[i]小的数量
        for(int j=i+1;j<n;j++) if(list[j]<list[i]) num++;
        sum+=num*perm(n-i-1);
    }
    return sum;
}
bool rePerm(int list[],int n)
{
    int i;
    for(i=n-2;i>=0;i--)
    {
        if(list[i]<list[i+1]) break;
    }
    if(-1==i) return false;
    else
    {
        int j=n-1;
        while(list[j]<list[i]) j--;
        swap(list[i],list[j]);
        reverse(&list[i+1],&list[n-1]);
        return true;
    }
}
int main()
{
    int n;
    int list[100];
    cin>>n;
    for(int i=0;i<n;i++) cin>>list[i];
    cout<<order(list,n)<<endl;
    if(rePerm(list,n))
    {
        for(int i=0;i<n;i++) cout<<list[i]<<' ';
    }
    else cout<<-1;
    return 0;
}