[LeetCode] Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

问题描述：给定n和k，获得[1, 2,..., n]的排列的从小到大的第k个序列。

最笨的办法就是将所有的排列都求出来，然后对其进行排序，然后取第k个。

看看上面那个例子，取第一个数字时可以将上面的序列进行分组，开始两个为一组，中间两个为一组，最后两个为一组。当k为1或者2时，第一位为1，当k为3或者4时，第一位为2，当k为5或者6时，第一位为3。也就是说当求第一位时，将序列分为n组，每组(n - 1)!个序列，然后求出第k个序列所在的组的序号group，就能够得出该位上的数字（该位上的数字即是当前可以取值的所有数字的第group个数字），然后更新k，将k减去前面组的序列个数，就得到要求的第k个序列在该组序列中的序号k'。然后求剩下的n - 1个数字的第k'个序列。

#include 
  
   
#include 
   
     using namespace std; class Solution { string s; public: int factorial(int n) { if(n == 1) return n; return n * factorial(n- 1); } string get_per(int n, int k) { if(n == 1) return string(1, s[n - 1]); int group = 0, n_tmp = n, fac = factorial(n - 1); string str; if(k % fac) group = k / fac + 1; else group = k / fac; k -= fac * (group - 1); str += s[group - 1]; s.erase(s.begin() + group - 1); str += get_per(--n, k); return str; } string getPermutation(int n, int k) { int n_tmp = n; char ch = '1'; s.clear(); while(n_tmp--) { s += ch; ++ch; } return get_per(n, k); } }; int main(int argc, char *argv[]) { Solution sol; for(int i = 1; i <= 24; ++i) { string str = sol.getPermutation(4, i); cout << str << endl; } return 0; }