Lexicographic permutations

Problem 24
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

题目解析

本题是求0-9这十个数字的全排列中，按字典序排列中第1000000个数是多少？

(ps:做这道题的时候我的第一反应就是暴力，因为我想1000000也不是很大，暴力就随便求出来了，然后就解了一下的。然后我就搜题解看了一下的。欧拉计划就是为了思维方式的锻炼，一味的暴力实在不妥。)

9个数的全排列有9！=362880个数，所以把第一位确定为0的时候一共排了362880个数，然后1000000/9！=2，所以以0开头和以1开头的全排列都在1000000之前。然后第一个数字就可以确定为2了。
以此类推判断第2位，后面有8位数。1000000减去2*9！之后还有6个8！。所以在剩余的9个数中找第7位，就是7了。
.
.
.
最后判断的结果就是2783915460。

程序代码 C

#include <stdio.h>
#include <string.h>
int f(int n){       //求n的阶乘的函数 
    if(n==0)
        return 1;
    return f(n-1)*n;
}

int main()
{
    int i,j,k;
    int a[20],b[20];
    while(scanf("%d",&k)!=EOF){
        int c[10]={0,1,2,3,4,5,6,7,8,9};
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        printf("0-9的全排列中的第%d个为：\n",k); 
        for(i=1;i<10;i++)       //求1-9所有数的阶乘 
            a[i]=f(i);
        k--;
        for(i=9;i>0&&k;i--){    //判断1000000中有几个i位全排列 
            b[i]=k/a[i];
            k=k%a[i];
        }
        for(i=9;i>=0;i--){      //根据每种位数的全排列求结果 
            printf("%d",c[b[i]]);
            for(j=b[i];j<=i;j++){
                c[j]=c[j+1];
            }
        }
        printf("\n");
    }
    return 0;
}