# Permutation Index ### Source - lintcode: [(197) Permutation Index](http://www.lintcode.com/en/problem/permutation-index/) ~~~ 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. ~~~ ### 題解 做過 next permutation 系列題的話自然能想到不斷迭代直至最后一個，最后返回計數器的值即可。這種方法理論上自然是可行的，但是最壞情況下時間復雜度為 O(n!)O(n!)O(n!), 顯然是不能接受的。由于這道題只是列出某給定 permutation 的相對順序(index), 故我們可從 permutation 的特點出發進行分析。 以序列`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`. 以上分析看似正確無誤，實則有個關鍵的漏洞，在排定第一個數2后，第二位數只可為1或者4，而無法為2, 故在計算最終的 index 時需要動態計算某個數的相對大小。按照從低位到高位進行計算，我們可通過兩重循環得出到某個索引處值的相對大小。 ### 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 0; long index = 1; long factor = 1; for (int i = A.length - 1; i >= 0; i--) { int rank = 0; for (int j = i + 1; j < A.length; j++) { if (A[i] > A[j]) rank++; } index += rank * factor; factor *= (A.length - i); } return index; } } ~~~ ### 源碼分析 注意 index 和 factor 的初始化值，rank 的值每次計算時都需要重新置零，index 先自增，factor 后自乘求階乘。 ### 復雜度分析 雙重 for 循環，時間復雜度為 O(n2)O(n^2)O(n2). 使用了部分額外空間，空間復雜度 O(1)O(1)O(1). ### Reference - [Permutation Index](http://www.geekviewpoint.com/java/numbers/permutation_index)