【2-6】排列的字典序问题

问题描述：
n 个元素{1,2,?, n }有 n!个不同的排列。将这 n!个排列按字典序排列，并编号为 0，1，…，
n!-1。每个排列的编号为其字典序值。例如，当 n=3 时，6 个不同排列的字典序值如下：
字典序值 0 1 2 3 4 5
排列 123 132 213 231 312 321
′编程任务：
给定 n 以及 n 个元素{1,2,?, n }的一个排列，计算出这个排列的字典序值，以及按字
典序排列的下一个排列。
′数据输入：
由文件 input.txt 提供输入数据。文件的第 1 行是元素个数 n。接下来的 1 行是 n 个元素
{1,2,?, n }的一个排列。
′结果输出:
程序运行结束时，将计算出的排列的字典序值和按字典序排列的下一个排列输出到文件
output.txt 中。文件的第一行是字典序值，第 2 行是按字典序排列的下一个排列。
输入文件示例 输出文件示例
input.txt output.txt
8
2 6 4 5 8 1 7 3
8227
2 6 4 5 8 3 1 7

【题解】

比较经典的做法是用康拓展开直接求。
这里介绍另外一种做法。
就是对于1..n的一个排列a[1..n]
首先它肯定大于首元素为1..a[1]-1的排列。
这样的排列有(a[1]-1)(n-1)!个
然后我们接着考虑a[2..n]
我们可以这样。
把a[2..n]当中比a[1]大的数字都减去1.
这样的话。
a[2..n]就是1..n-1的一个排列了。
我们的问题转化成求a[2..n-1]的排名。
这样我们就还是能用相同的方法来做这个问题了。
即累加(a[2]-1)(n-2)!
以此类推便可以解决这个问题了。
逆过来的话。
也还是很简单。
显然
a[i]=p/(n-i)! + 1
然后for i 从n到1,对于j>i,如果a[i]<=a[j],那么a[j]递增

【代码】

#include <cstdio>
#define ll long long
using namespace std;

const int N = 15;

int n;
int a[N+10],b[N+10];
ll f[N+10];

int main(){
    f[0] = 1;
    for (int i = 1;i <= N;i++) f[i] = f[i-1]*i;
    scanf("%d",&n);
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    ll ans1 = 0;
    for (int i = 1;i <= n;i++){
        ans1+=(a[i]-1)*f[n-i];
        for (int j = i+1;j <= n;j++)
            if (a[j]>a[i])
                a[j]--;
    }
    printf("%I64d\n",ans1);
    //ans1++让你求出字典序为ans1的序列
    ans1++;
    for (int i = 1;i <= n;i++){
        b[i] = ans1/f[n-i];
        ans1-=b[i]*f[n-i];
        b[i]++;
    }
    for (int i = n-1;i>=1;i--){
        for (int j = i+1;j<=n;j++){
            if(b[j]>=b[i]) b[j]++;
        }
    }
    for (int i = 1;i <= n;i++){
        printf("%d ",b[i]);
    }
    return 0;
}

【2-6】排列的字典序问题

原文：https://www.cnblogs.com/AWCXV/p/11635845.html