https://segmentfault.com/a/1190000004683277
在计算最终的 index 时需要动态计算某个数的相对大小。我们可通过两重循环得出到某个索引处值的相对大小。
以4,1,2为例，4为第3大数,1为剩余序列第1大数，2为剩余序列第1大数，
故表达式为：(3-1)*2! + (1-1)*1! + (1-1)*0! + 1 = 5
以2,4,1为例，2为第2大数，4为剩余序列第2大数，1为剩余序列第1大数
故表达式为：(2-1)*2! + (2-1)*1! + (1-1)*0! + 1 = 4
这后面这个1一定要加，因为前面算的都是比该数小的数，加上这个1，才是该数是第几大数。
2！表示当时当前位后面还有两位，全排列有2！种
https://segmentfault.com/a/1190000004683277
X. DFS
http://lintcode.peqiu.com/content/lintcode/permutation_index.html
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.
Given [1,2,4], return 1.
http://algorithm.yuanbin.me/zh-hans/exhaustive_search/permutation_index.html
例如[4,2,1]，对于4, 比4小的有2和1， 在4这一位，对应的factor为2! (factor的含义是在当前位置数值指定的情况下，变化index大于当前数值的数字，所可能的到的不同排列的个数), 因此在index=0时，可能的排列一共有2*2!. 同理，对于[4,2,1],结果为2*2! + 1*1 + 0*1 + 1 = 6
以上分析看似正确无误，实则有个关键的漏洞，在排定第一个数2后，第二位数只可为1或者4，而无法为2,故在计算最终的 index 时需要动态计算某个数的相对大小。按照从低位到高位进行计算，我们可通过两重循环得出到某个索引处值的相对大小。
注意 index 和 factor 的初始值，rank 的值每次计算时都需要重新置零，index 先自增，factorial 后自乘求阶乘。
public long permutationIndex(int[] A) {
if (A == null || A.length == 0) return 0L;
long index = 1, fact = 1;
for (int i = A.length - 1; i >= 0; i--) {
// get rank in every iteration
int rank = 0;
for (int j = i + 1; j < A.length; j++) {
if (A[i] > A[j]) rank++;
}
index += rank * fact;
fact *= (A.length - i);
}
return index;
}在计算最终的 index 时需要动态计算某个数的相对大小。我们可通过两重循环得出到某个索引处值的相对大小。
以4,1,2为例，4为第3大数,1为剩余序列第1大数，2为剩余序列第1大数，
故表达式为：(3-1)*2! + (1-1)*1! + (1-1)*0! + 1 = 5
以2,4,1为例，2为第2大数，4为剩余序列第2大数，1为剩余序列第1大数
故表达式为：(2-1)*2! + (2-1)*1! + (1-1)*0! + 1 = 4
这后面这个1一定要加，因为前面算的都是比该数小的数，加上这个1，才是该数是第几大数。
2！表示当时当前位后面还有两位，全排列有2！种
6 public long permutationIndex(int[] A) { 7 // Write your code here 8 long res = 0; 9 int n = A.length; 10 long fact = 1; 11 for (int i=1; i<n; i++) { 12 fact *= i; //fact should at last equal (n-1)! 13 } 14 int initial = n-1; //use to update factorial 15 for (int i=0; i<n; i++) { 16 long count = 0; 17 for (int j=i; j<n; j++) { 18 if (A[i] >= A[j]) { 19 count++; 20 } 21 } 22 res += (count-1)*fact; 23 if (initial != 0) { 24 fact /= initial; 25 initial--; 26 } 27 } 28 res = res + 1; 29 return res; 30 }
https://segmentfault.com/a/1190000004683277
搞一个哈希表，存储数组A中每一位A[i]的后面小于它的数的个数count。
为什么这样做呢，因为按照lexicographical order，小的数应该排在前面。那么A[i]后面小于A[i]的数有count个，而i前面又应该有n-i-1位，有(n-1-i)的阶乘种排列的可能，所以应该排在A[i]之前的可能排列就有
为什么这样做呢，因为按照lexicographical order，小的数应该排在前面。那么A[i]后面小于A[i]的数有count个，而i前面又应该有n-i-1位，有(n-1-i)的阶乘种排列的可能，所以应该排在A[i]之前的可能排列就有
count * (n-1-i)!个：所以遍历A[]中每一个数，计算在其之前的自然排列的数目，这些数目相加之和存入res，那么res的下一个数字就是现在数组A[]的排列。
对题目有了思索和理解之后，可以找找简化一点的办法。有没有可能不使用HashMap，也能够记录阶乘呢？只要从最后一位
fact = 1开始, 向高位阶乘，直到最高位fact = A.length!。 public long permutationIndex(int[] A) {
int n = A.length;
long res = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i+1; j < n; j++) {
if (A[i] > A[j]) count++;
}
map.put(A[i], count);
}
for (int i = 0; i < n; i++) {
long fact = 1;
for (int j = n-1-i; j > 0; j--) {
fact *= j;
}
res += map.get(A[i]) * fact;
}
return ++res;
} public long permutationIndex(int[] A) {
if (A == null || A.length == 0) return 0;
long fact = 1, index = 0;
for (int i = A.length-1; i >= 0; i--) {
int rank = 0;
for (int j = i+1; j < A.length; j++) {
if (A[j] < A[i]) rank++;
}
index += rank * fact;
fact *= (A.length-i);
}
return index+1;
}
//这种思路是从高位向低位计算当前位剩余排列总数，阶乘逐位减小，理解起来就没有那么直观了。
public long permutationIndex(int[] A) {
if (A == null || A.length == 0) return 0;
long index = 0, fact = 1;
for (int i = 1; i <= A.length; i++) fact *= i;
for (int i = 0; i < A.length; i++) {
int rank = 0;
for (int j = i+1; j < A.length; j++) {
if (A[j] < A[i]) rank++;
}
fact /= (A.length-i);
index += rank * fact;
}
return index+1;
}long fac(int numerator) { long now = 1; for (int i = 1; i <= numerator; i++) { now *= (long) i; } return now; } long generateNum(HashMap<Integer, Integer> hash) { long denominator = 1; int sum = 0; for (int val : hash.values()) { if(val == 0 ) continue; denominator *= fac(val); sum += val; } if(sum==0) { return sum; } return fac(sum) / denominator; } public long permutationIndex(int[] A) { HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); for (int i = 0; i < A.length; i++) { if (hash.containsKey(A[i])) hash.put(A[i], hash.get(A[i]) + 1); else { hash.put(A[i], 1); } } long ans = 0; for (int i = 0; i < A.length; i++) { for (int j = i + 1; j < A.length; j++) { if (A[j] < A[i]) { hash.put(A[j], hash.get(A[j])-1); ans += generateNum(hash); hash.put(A[j], hash.get(A[j])+1); } } hash.put(A[i], hash.get(A[i])-1); } return ans+1; }http://www.tuwenzhai.com/d/94558250-815c-4b50-95f3-68d2ed883cd1/ab63e816-26ce-4339-bf94-dd4c325bb3ea
X. DFS
http://lintcode.peqiu.com/content/lintcode/permutation_index.html
1, 2, 4为例，其不同的排列共有3!=6种，以排列[2, 4, 1]为例，若将1置于排列的第一位，后面的排列则有2!=2种。将2置于排列的第一位，由于[2, 4, 1]的第二位4在1, 2, 4中为第3大数，故第二位可置1或者2，那么相应的排列共有2 * 1! = 2种，最后一位1为最小的数，故比其小的排列为0。综上，可参考我们常用的十进制和二进制的转换，对于[2, 4, 1], 可总结出其排列的index为2! * (2 - 1) + 1! * (3 - 1) + 0! * (1 - 1) + 1.