Permutation Sequence

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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):
 "123"
 "132"
 "213"
 "231"
 "312"
 "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Solution: k = 3 return "231"

代码：

 class Solution {  
 public:  
   // permuation problem, not graph problem  
   string getPermutation(int n, int k) {  
     // index k starting from 0.  
     string num, res;  
     int total = 1;  
     for (int i = 1; i <= n; ++i) { // push back "123"  
       num.push_back(i + '0');  
       total *= i;  
     }  
   
     k--; // index starting from 0  
     while (n) {  
       total /= n;  
       int i = k / total; // i-th group (start from 0)  
       k %= total; // (start from 0) k-th element i-th group  
       res.push_back(num[i]);  
       num.erase(i, 1);  
       n--;  
     }  
     return res;  
   }  
 };