C++ | Kth Permutation
\tclass Solution {\npublic:\n    \n\t// function to calculate factorial of a number with a little adjustment \n\t//so that it does not go out of the memory boun
\tclass Solution {\npublic:\n    \n\t// function to calculate factorial of a number with a little adjustment \n\t//so that it does not go out of the memory bound\n    long long fact(long long n, long long t)\n    {\n        if(n == 0 || n == 1 || n == t) return 1;\n        return n * fact(n - 1,t);\n    }\n\t\n\t//function to calculate total permutation keeping a character at first index\n    int calculate(char ch, map<char,int>& mp, int len)\n    {\n        int k = ch==\'H\'?mp[\'H\']-1:mp[\'H\'];\n        int j = ch==\'V\'?mp[\'V\']-1:mp[\'V\'];\n        \n        long long sum =  fact(len,max(k,j));\n        sum /= fact(min(k,j),1);\n        \n        return (int)sum;\n    }\n    \n    string kthper(int n, int k, map<char,int>& mp)\n    {\n        if(mp.size() == 1)\n        {\n            string temp = "";\n            for(auto it:mp)\n            {\n                while(it.second > 0)\n                {\n                    temp.push_back(it.first);\n                    it.second--;\n                }\n            }\n            return temp;\n        }\n        \n        string res = "";\n        for(auto it: mp)\n        {\n            int cal = calculate(it.first, mp, n-1);\n            if(cal < k)\n            {\n                k -= cal;\n            }\n            else\n            {\n                res.push_back(it.first);\n                mp[it.first]--;\n                if(mp[it.first] == 0) mp.erase(it.first);\n                res += kthper(n-1,k,mp);\n                break;\n            }\n        }\n        return res;   \n    }\n    \n    string kthSmallestPath(vector<int>& des, int k) {\n        int n = des[0]+1;\n        int m = des[1]+1;\n        string str = "";\n        for(int i=0;i<m-1;i++)\n        {\n            str += "H";\n        }\n        for(int i=0;i<n-1;i++)\n        {\n            str += "V";\n        }\n        \n        map<char,int> mp;\n        for(auto ch : str)\n        {\n            mp[ch]++;\n        }\n        return kthper(str.size(),k,mp);\n    }\n\t};\n\nWhat i am doing in this solution is , I am picking the smallest character from the string and keeping that character at the first index and finding all possible permutations of rest of the character. Just like you have done in your highschool at the time of permutation and combinations lecture (finding the rank of a word in a dictionary).\nLets say there are x total permutations if x < k, that means in the kth permutation the letter currently on first index can not be at first index as all the permutations keeping that at first index is less than k; decrease k by x as i have already checked x permutations.\nNow i will put the next greater character i.e V at first index and calculate all possible permutations and check if no of permutations are less than k (which it should be as there are only 2 char in string) that means V should be my first character in kth permutation.\nNow i will just call recursion for the rest of the string and finally will return the ans;\nPS: IT USES THE CONCEPT OF "FINDING THE RANK OF A WORD IN A DICTIONARY".
['C', 'Probability and Statistics']