Friday, April 15, 2016

LintCode - Permutation Index

https://segmentfault.com/a/1190000004683277
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

+

``````    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;
}``````
http://www.cnblogs.com/EdwardLiu/p/5104310.html

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

``````    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;
}``````
http://www.jiuzhang.com/solutions/permutation-index/
``` 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