1209_排列的字典序

Description

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

有多个测试用例. 每个测试用例由两行组成, 第一行是一个自然数 n(n ≤ 20), 第二行是 { 1, 2, …, n } 的一个排列. 输入直至没有数据或者 n=0 为止.

Output

对于每个测试用例输出两行, 第一行是给定排列的序值, 第二行是给定排列按字典序的下一个排列.

Sample Input

8
2 6 4 5 8 1 7 3

Sample Output

8227
2 6 4 5 8 3 1 7

参考

#include<stdio.h>
#include<iostream>
using namespace std;
int a[25];
int b[25];
int fact(int m){
    
	if(m == 0)
		return 1;
	return m * fact(m - 1);
}
int nextStr(int n)
{
    
    int flag=1;
    int i,j;
    int left=n-1;
    while(b[left]<b[left-1]){
    
        left--;
        if (left<0){
    
            flag=0;
            break;
        }
    }
    if (!flag)
        return flag;
    left--;  
    int right=n-1;
    while(b[right]<b[left])
        right--;
    int temp;
    temp=b[left]; b[left]=b[right]; b[right]=temp;
    i=left+1;
    j=n-1;
    while(i<j){
    
        temp=b[i]; b[i]=b[j]; b[j]=temp;
        i++;
        j--;
    }
    return flag;

}
int main()
{
    
    int n;
    int k;
    while(cin>>n) {
    
        for (int i = 0; i < n;++i){
    
            cin >> k;
            a[i] = k;
            b[i] = k;
        }
        int i, j;
        int count = 0;
        for(i = 0;i < n;i ++){
    
            count = count + (a[i] - 1) * fact(n - i - 1); 
            for(j = i + 1;j < n;j ++){
    //因为a[i]后面的数不能跟前面的重复，所以循环剪掉大于a[i]的数 
                if(a[j] > a[i]){
    
                    a[j] --;
                }
                
            }
        }
        cout << count << endl;
        nextStr(n);
        for (int i = 0; i < n;++i) {
    
            cout << b[i] << " ";
        }
        cout << endl;
    }
    return 0;
}