# Permutation Index

## Question

### Problem Statement

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.

## 题解

### Python

class Solution:
# @param {int[]} A an integer array
# @return {long} a long integer
def permutationIndex(self, A):
if A is None or len(A) == 0:
return 0

index = 1
factor = 1
for i in xrange(len(A) - 1, -1, -1):
rank = 0
for j in xrange(i + 1, len(A)):
if A[i] > A[j]:
rank += 1

index += rank * factor
factor *= (len(A) - i)

return index


### C++

class Solution {
public:
/**
* @param A an integer array
* @return a long integer
*/
long long permutationIndex(vector<int>& A) {
if (A.empty()) return 0;

long long index = 1;
long long factor = 1;
for (int i = A.size() - 1; i >= 0; --i) {
int rank = 0;
for (int j = i + 1; j < A.size(); ++j) {
if (A[i] > A[j]) ++rank;
}
index += rank * factor;
factor *= (A.size() - i);
}

return index;
}
};


### Java

public class Solution {
/**
* @param A an integer array
* @return a long integer
*/
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;
}
}