Permutation Sequence

Question

Problem Statement

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

Example

For n = 3, all permutations are listed as follows:

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

If k = 4, the fourth permutation is "231"

Note

n will be between 1 and 9 inclusive.

Challenge

O(n*k) in time complexity is easy, can you do it in O(n^2) or less?

题解

和题 Permutation Index 正好相反，这里给定第几个排列的相对排名，输出排列值。和不同进制之间的转化类似，这里的『进制』为1!, 2!..., 以n=3, k=4为例，我们从高位到低位转化，直觉应该是用 k/(n-1)!, 但以 n=3,k=5 和 n=3,k=6 代入计算后发现边界处理起来不太方便，故我们可以尝试将 k 减1进行运算，后面的基准也随之变化。第一个数可以通过(k-1)/(n-1)!进行计算，那么第二个数呢？联想不同进制数之间的转化，我们可以通过求模运算求得下一个数的k-1, 那么下一个数可通过(k2 - 1)/(n-2)!求得，这里不理解的可以通过进制转换类比进行理解。和减掉相应的阶乘值是等价的。

Python

  1. class Solution:
  2.     """
  3.     @param n: n
  4.     @param k: the k-th permutation
  5.     @return: a string, the k-th permutation
  6.     """
  7.     def getPermutation(self, n, k):
  8.         # generate factorial list
  9.         factorial = [1]
  10.         for i in xrange(1, n + 1):
  11.             factorial.append(factorial[-1] * i)
  13.         nums = range(1, n + 1)
  14.         perm = []
  15.         for i in xrange(n):
  16.             rank = (k - 1) / factorial[n - i - 1]
  17.             k = (k - 1) % factorial[n - i - 1] + 1
  18.             # append and remove nums[rank]
  19.             perm.append(nums[rank])
  20.             nums.remove(nums[rank])
  21.         # combine digits
  22.         return "".join([str(digit) for digit in perm])

C++

  1. class Solution {
  2. public:
  3.     /**
  4.       * @param n: n
  5.       * @param k: the kth permutation
  6.       * @return: return the k-th permutation
  7.       */
  8.     string getPermutation(int n, int k) {
  9.         // generate factorial list
  10.         vector<int> factorial = vector<int>(n + 1, 1);
  11.         for (int i = 1; i < n + 1; ++i) {
  12.             factorial[i] = factorial[i - 1] * i;
  13.         }
  14.         // generate digits ranging from 1 to n
  15.         vector<int> nums;
  16.         for (int i = 1; i < n + 1; ++i) {
  17.             nums.push_back(i);
  18.         }
  20.         vector<int> perm;
  21.         for (int i = 0; i < n; ++i) {
  22.             int rank = (k - 1) / factorial[n - i - 1];
  23.             k = (k - 1) % factorial[n - i - 1] + 1;
  24.             // append and remove nums[rank]
  25.             perm.push_back(nums[rank]);
  26.             nums.erase(std::remove(nums.begin(), nums.end(), nums[rank]), nums.end());
  27.         }
  28.         // transform a vector<int> to a string
  29.         std::stringstream result;
  30.         std::copy(perm.begin(), perm.end(), std::ostream_iterator<int>(result, ""));
  32.         return result.str();
  33.     }
  34. };

Java

  1. class Solution {
  2.     /**
  3.       * @param n: n
  4.       * @param k: the kth permutation
  5.       * @return: return the k-th permutation
  6.       */
  7.     public String getPermutation(int n, int k) {
  8.         if (n <= 0 && k <= 0) return "";
  10.         int fact = 1;
  11.         // generate nums 1 to n
  12.         List<Integer> nums = new ArrayList<Integer>();
  13.         for (int i = 1; i <= n; i++) {
  14.             fact *= i;
  15.             nums.add(i);
  16.         }
  18.         // get the permutation digit
  19.         StringBuilder sb = new StringBuilder();
  20.         for (int i = n; i >= 1; i--) {
  21.             fact /= i;
  22.             // take care of rank and k
  23.             int rank = (k - 1) / fact;
  24.             k = (k - 1) % fact + 1;
  25.             // ajust the mapping of rank to num
  26.             sb.append(nums.get(rank));
  27.             nums.remove(rank);
  28.         }
  30.         return sb.toString();
  31.     }
  32. }

源码分析

源码结构分为三步走，

  1. 建阶乘数组
  2. 生成排列数字数组
  3. 从高位到低位计算排列数值

复杂度分析

几个 for 循环，时间复杂度为 O(n), 用了与 n 等长的一些数组，空间复杂度为 O(n).

Reference