Permutation Index
Source
- lintcode: 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.
题解
4个数的排列有4！种。当我们知道第一位数的时候，还有3！种方式，当知道第二位数时候还有2！种方式，当知道第三位数的时候还有1！种方式，前面三位数都确定的时候，最后一位也确定了。
对4个数的排列，各位的权值为：3！，2！，1！，0！。第一位之后的数小于第一位的个数是x，第二位之后的数小于第二位的个数是y，第三位之后的数小于第三的个数是z，第四位之后的数小于第四位的个数是w，则abcd排列所在的序列号:index = x3！+y2!+z*1!
为什么会有上面的结论呢？举个例子： 假如 4213 我们得到 3*3! + 1*2! + 0*1! = 20 之所以用3乘以3的阶乘是因为第一位是4 后面2，1，3有三个数都小于4，也就是说在排序的时候第一位为1或者2或者3都会排在第一位为4的前面, 所以得到 3!+3!+3! = 3*3!
例如
4213；x= 3，y = 1，z=0，index = 18+2=20
123；x = 0，y=0，index = 0
321；x= 2，y=1，index = 2*2！+1*1！ = 5
这里的下标是从0开始的, 所以返回值要加1
Python
class Solution:
# @param {int[]} A an integer array
# @return {long} a long integer
def permutationIndex(self, A):
# Write your code here
result=1
factor=1
position=2
for i in range(len(A)-2, -1, -1):
num=0
for j in range(i+1, len(A)):
if A[j]<A[i]:
num+=1
result += num*factor
factor *= position
position += 1
return result