例1 {1,2,3,4,5}的全排列,并且已经从小到大排序完毕 (1)找出第96个数 首先用96-1得到95 用95去除4! 得到3余23 有3个数比它小的数是4 所以第一位是4 用23去除3! 得到3余5 有3个数比它小的数是4但4已经在之前出现过了所以第二位是5(4在之前出现过,所以实际比5小的数是3个) 用5去除2!得到2余1 有2个数比它小的数是3,第三位是3 用1去除1!得到1余0 有1个数比它小的数是2,第二位是2 最后一个数只能是1 所以这个数是45321 (2)找出第16个数 首先用16-1得到15 用15去除4!得到0余15 用15去除3!得到2余3 用3去除2!得到1余1 用1去除1!得到1余0 有0个数比它小的数是1 有2个数比它小的数是3 但由于1已经在之前出现过了所以是4(因为1在之前出现过了所以实际比4小的数是2) 有1个数比它小的数是2 但由于1已经在之前出现过了所以是3(因为1在之前出现过了所以实际比3小的数是1) 有1个数比它小得数是2 但由于1,3,4已经在之前出现过了所以是5(因为1,3,4在之前出现过了所以实际比5小的数是1) 最后一个数只能是2 所以这个数是14352
题目 求出字符“abcdefghjklmnopq”的第9898999个全排列顺序
#include<iostream>
#include<vector>
#define N 17
using namespace std;
int cal(int n)
{
int x = 1;
for(int i = 1; i <= n; i++)
{
x *= i;
}
return x;
}
int main()
{
int n = 9898999;
vector<char> c,ve;
int u,v;
u = n;
//用于抽取数字
for(int i = 0; i < N; i++)
{
c.push_back(i+'a');
}
for(int i = N-1; i > 0; i--)
{
v = u%cal(i);
u = u/cal(i);
ve.push_back(c[u]);
c.erase(c.begin()+u);
u = v;
}
//将最后一个数提取出来
ve.push_back(c[0]);
for(int i = 0; i < N; i++)
{
cout << ve[i] ;
}
return 0;
}