[ 算法 ] 排列字典序问题

问题

n个元素有n！个不同的排序。将这n！个排列按字典序排列，并编号为0,1,...,n-1。每个排列的编号为其字典序值。

例如，当n=3时，6个不同排列的字典序值如下：

    字典序值   0   1   2   3   4   5

    排列     123 132 213 231 312 321

代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

//进行数交换
void takeSwitch(int* a, int* b)
{
    long long t;
    t = *a;
    *a = *b;
    *b = t;
}

int main() {
    int n, i, j, k, t, order[100];
    long long lis, f[100], mid, h;
    f[0] = 1;
    for (i = 1; i <= 22; i++)
        f[i] = f[i - 1] * i;
    while (scanf("%d", &n) != EOF)
    {
        for (i = 0; i < n; i++)
            scanf("%d", &order[i]);
        if (n == 1)
            printf("0\n");
        else if (n >= 2)
        {
            lis = 0;
            for (i = 0, k = n - 1; i < n - 1; i++, k--)
            {
                t = 0;
                for (j = 0; j < i; j++)
                    if (order[j] < order[i])    t++;
                lis += (order[i] - 1 - t) * f[k];
            }
            printf("%lld\n", lis);

            for (i = n - 2; i >= 0; i--)
            {
                if (order[i] < order[i + 1])
                {
                    j = i;
                    for (k = n - 1; k > j; k--)
                    {
                        if (order[k] > order[j])
                        {
                            mid = j + (n - j) / 2;
                            takeSwitch(&order[j], &order[k]);
                            for (j++, h = 1; j <= mid; j++, h++)
                                takeSwitch(&order[j], &order[n - h]);
                        }
                    }
                    break;
                }
            }

            for (i = 0; i < n - 1; i++)
                printf("%d ", order[i]);
            printf("%d\n", order[i]);
        }
    }
}