原题
LintCode 197. Permutation Index
Description
Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.
Example
Given [1,2,4], return 1.
解题
题意是给定的一组数字，这组数字按照字典序全排列，求原顺序在这个全排列中的位置。
耿直解法可以直接求全排列，然后找到原顺序的位置即可。
其他解法：
首先举个例子，4,5,3三个数字
正常的字典序是
3,4,5
3,5,4
4,3,5
4,5,3
5,3,4
5,4,3
第一个数字
可以发现，开头的数字不是4的时候其实可以直接跳过。当排列到4,5,3这个顺序时，实际上还没有到达5开头，也就是说需要跳过的是比4小的数字开头时候的全排列，在这里也就是要跳过3。
这时候我们跳过了3开头的全排列一共 (3 -1) ! = 2个
第二个数字
到了4开头的全排列，我们的要求4,5,3。按照上一步相同的逻辑，不是5作为第二个数字的排列都可以跳过，也就是要跳过第二个位置比5小的排列，在这里就是要跳过第二个数字是3的排列
这时候我们跳过了3作为第二个数字的排列一共 (3 - 2) ! = 1个
最后一个数字
到达最后一个数字3，已经满足了要求，那么此时的位置其实就是前面跳过的总数+1 2 + 1 + 1 = 4
总结
对于全排列中的每一位，我们都跳过比目标顺序该位数字小的数字填充这个位置时候的排列。
比如上例中，在全排列的第一位，目标顺序的该位为4，那么我们就需要跳过所有比4小的数字（本例中只有3）填充第一位的时候的排列。
直到最后一位，将跳过的总数相加再+1即可。
代码
class Solution {
public:
/*
* @param A: An array of integers
* @return: A long integer
*/
long long permutationIndex(vector<int> A) {
// write your code here
int n = A.size();
if (n == 1)
return 1;
// 第一步 计算比每个数字小的数字有多少个
// 比如4,5,3这个组合，计算结果是A={1,2,0}
long long smaller[30];
for (int i = 0; i < n; ++i) {
smaller[i] = 0;
for (int j = 0; j < n; ++j)
if (A[j] < A[i])
smaller[i] ++;
}
// 提前计算阶乘结果，方便以后使用
long long F[15];
F[0] = 1;
for (int i = 1; i < 15; ++i)
F[i] = F[i - 1] * i;
// 记录跳过的总数
long long sum = 0;
for (int i = 0, k = n - 1; i < n - 1; i++, k--) {
// 对于每一位，跳过比它小的数填充时的情况
sum += (long long)(smaller[i]) * F[k];
// 使用完这个数字，比它大的数的samller要-1
// 比如4填充了第一位，比5小的数字应该从2个(4,3)变为1一个(3)
for (int j = i + 1; j < n; ++j)
if (smaller[i] < smaller[j])
smaller[j]--;
}
// 结果 为跳过数+1
return sum + 1;
}
};
