LIKE CODING: MJ [2]

LIKE CODING: MJ [2]
Questions: Similar to LeetCode Permutation Sequence [1] except the numbers in nums are not unique. In Test, there are 4 numbers whose permutations are in increasing order, find the sequence number (1-based) of one of its permutation in the sequence. Eg., if nums=[2 1 2 3] it should return 4; if nums=[3 1 2 2] it should return 10.

Test:
 1 2 2 3---1
 1 2 3 2---2
 1 3 2 2---3
 2 1 2 3---4
 2 1 3 2---5
 2 2 1 3---6
 2 2 3 1---7
 2 3 1 2---8
 2 3 2 1---9
 3 1 2 2---10
 3 2 1 2---11
 3 2 2 1---12
http://www.mitbbs.com/article_t/JobHunting/33021689.html
给一手有序列n张的扑克牌, 无视花色, 只视数字(倒如: 4 9 7 7), 牌由无限副扑克抽
出来, 所以一个数字也能出现无数次,  求该序列在该手牌所能组合的所有序例中的顺
增的位置:

例: 4 9 7 7 

4 7 7 9 – 1
4 7 9 7 – 2
4 9 7 7 – 3  ← 
in general case, the possible number of 
permutation of numbers with possible duplication can be calculated with, e.g
. 
a1,a1,...a1,a2,a2...a2,a3,a3,...a3,ak,ak,...ak,
let's say we have i1 numbers of a1, i2 numbers of a2, ...ik numbers of ik, 
and sum(i1, ...ik) =n, the number of possible permutation is:
n! / i1! * i2! * i3! ...* ik!

use this formula, you can quickly find out the number of sequence, e.g. in 
your example, when start with 4, the number of sequence is 3! / 2! = 3
比如拿到41977这手牌 第一个数为1则index一定比41977小 个
数等于4 7 7 9全排列

第一个数选4 第二个数没有可能比1小 直接选1 第三个数选7则index一定比41977小 个
数等于 7 9全排列

所以41977的index等于 4!/2! ＋2!

    int factorial(int n){

        if(!n) return 1;

        return n*factorial(n-1);

    }

    int getPrevGroupsCnt(unordered_map<int, int> &digcnt, int v, vector<int> &digits){

        int i = 0, ret = 0;

        for(; i<digits.size(); ++i){

            if(digits[i]==v) break;//not count in the group staring with v

            unordered_map<int, int> dc = digcnt;

            dc[digits[i]]--;

            int count = 1, total = 0;

            for(auto it:dc){

                count *= factorial(it.second);

                total += it.second;

            }

            ret += factorial(total)/count;

        }

        digcnt[v]--;

        if(digcnt[v]==0) digits.erase(digits.begin()+i);

        return ret;

    }

    int getPermutation(vector<int> nums) {

        vector<int> nums_sort = nums;

        sort(nums_sort.begin(), nums_sort.end());

        unordered_map<int, int> digcnt;

        int n = nums_sort.size();

        vector<int> digits;

        for(int i=0; i<n; ++i){

            digcnt[nums_sort[i]]++;

            if(i==0||nums_sort[i]!=nums_sort[i-1]) digits.push_back(nums_sort[i]);

        }

 

        int seq = 0;

        for(int i=0; i<n; ++i){

            int v = nums[i];

            int c_groups = getPrevGroupsCnt(digcnt, v, digits);

            seq += c_groups;

        }

        return seq+1;

    }

};

 

int main(){

  Solution sol;

  vector<int> nums = {3,2,2,1};

  cout<<"seq is"<<sol.getPermutation(nums)<<endl;

Read full article from LIKE CODING: MJ [2]