permutation-sequence.cpp

// Time:  O(n^2)
// Space: O(n)

class Solution {
public:
    /**
     * @param n: n
     * @param k: the kth permutation
     * @return: return the k-th permutation
     */
    string getPermutation(int n, int k) {
        vector<int> nums;
        int total = 1;
        for (int i = 1; i <= n; ++i) {
            nums.emplace_back(i);
            total *= i;
        }

        // Cantor Ordering:
        // Construct the k-th permutation with a list of n numbers
        // Idea: group all permutations according to their first number (so n groups, each of
        // (n - 1)! numbers), find the group where the k-th permutation belongs, remove the common
        // first number from the list and append it to the resulting string, and iteratively
        // construct the (((k - 1) % (n - 1)!) + 1)-th permutation with the remaining n-1 numbers
        int group = total;
        stringstream output;
        while (n > 0) {
            group /= n;
            int idx = (k - 1) / group;
            output << nums[idx];
            nums.erase(nums.begin() + idx);
            k = (k - 1) % group + 1;
            --n;
        }

        return output.str();
    }
};