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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

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

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

---

Let's take n=3 as an example. Sequences starting with 1 have 2, which is 2!, and the same for 2 and 3. So if we'd like to get the the 3rd one, "213", its first number is 2, we can get it by (3-1)/ 2!). And the same for the remaining two digits. See as:

str = "", rank = 3, set = "123"

curr = (3-1)/2! = 1

str = "2", rank = rank % 2! = 1, set = "13"

curr = (1-1)/1! = 0

str = "21", rank = rank % 1! = 1, set = "3"

curr = (1-1)/1! = 0

str = "213", rank = rank % 0! = N/A, set = ""

I implemented recursive one in C++, iterative one in Python.

C++ Code:

/*
 * func: get_permutation_helper
 * goal: helper function for get_permutation
 * @param total: factorial number of n
 * @param n: the number of total unique numbers
 * @param k: the kth
 * @param num_set: number set
 * @result: final result string
 * return:
 */
void get_permutation_helper(int total, int n, int k, vector<int> &num_set, string &result){
    if(num_set.empty()){
        return;
    }
    //Get the first element
    total /= n;
    int curr = k / total;
    result += '0' + num_set[curr];
    num_set.erase(num_set.begin()+curr);
    get_permutation_helper(total, n-1, k % total, num_set, result);
}

/*
 * func: get_permutation
 * goal: given n and k, return the kth permutation sequence
 * @param n: the number of total unique numbers
 * @param k: the kth
 * return: kth permutation in string
 */
string get_permutation(int n, int k){
    string result = "";
    if(n < 1){
        return result;
    }
    //Compute the total number of permutations
    int total = 1;
    vector<int> num_set;
    for(int i=1; i<=n; ++i){
        total *= i;
        num_set.emplace_back(i);
    }
    if(k < 1 || k > total){
        return result;
    }

    
    //Construct the result
    get_permutation_helper(total, n, k-1, num_set, result);
    return result;
}

Python Code:

# func: get the kth permutation sequence
# @param n: there are total n! unique permutations
# @param k: the kth sequence
# @return: sequence in string
def get_permutation(n, k):
    total = reduce(lambda x, y: x * y, xrange(1, n+1))
    if n >= 1 and 1 <= k <= total:
        #Construct number set
        num_set = [i for i in xrange(1, n+1)]
        result = ''
        k -= 1
        while num_set:
            #Get current element
            curr = k / (total/n)
            result += str(num_set[curr])
            #Remove the element from num_set
            num_set.pop(curr)
            #Update remaining info
            total /= n
            n -= 1
            k %= total
        return result
    else:
        return ''