Permutation Index II

Question

Given a permutation which may contain repeated numbers, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

Example Given the permutation [1, 4, 2, 2], return 3.

Thoughts

这一题有了重复元素，就是要去掉重复的排列，其实很想排列组合问题，对于重复的数字我们应该去掉他们重复的组合，就是不在乎重复数字的重复排列，应该从原来的结果中除以重复元素个数的阶乘 用hashmap记录重复元素的个数

注意点

• 在loop中每遇到一个元素，都要重新建立一个hashmap来计算
• 元素自己也要先加入到hashmap中，不然在右边计算重复元素的时候就可能少掉自己的一次

Solution

class Solution:
    # @param {int[]} A an integer array
    # @return {long} a long integer
    def permutationIndexII(self, A):
        # Write your code here
        # Write your code here
        if not A:
            return None

        length = len(A)
        result = 1
        factor = 1
        for i in range(length-1, -1, -1):
            numSmaller = 0
            dic = {}
            #should record self one occurance, otherwise the self duplicate would miss 1
            dic[A[i]] = 1
            for j in range(i+1, length):
                if A[j] in dic:
                    dic[A[j]] += 1
                else:
                    dic[A[j]] = 1
                if A[i] > A[j]:
                    numSmaller += 1

            result += (numSmaller * factor / self.dupFac(dic))
            #factor for next number (i-1)
            factor *= length - i

        return result

    def dupFac(self, dic):
        if not dic:
            return 1
        dupFac = 1
        for num in dic:
            val = dic[num]
            fac = 1
            for i in range(1, val + 1):
                fac *= i
            dupFac *= fac
        return dupFac