Question

Source

• leetcode: Permutation Sequence | LeetCode OJ
• lintcode: (388) Permutation Sequence

Problem

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

Example

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

"123"
"132"
"213"
"231"
"312"
"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

class Solution:
  """
  @param n: n
  @param k: the k-th permutation
  @return: a string, the k-th permutation
  """
  def getPermutation(self, n, k):
    # generate factorial list
    factorial = [1]
    for i in xrange(1, n + 1):
      factorial.append(factorial[-1] * i)

    nums = range(1, n + 1)
    perm = []
    for i in xrange(n):
      rank = (k - 1) / factorial[n - i - 1]
      k = (k - 1) % factorial[n - i - 1] + 1
      # append and remove nums[rank]
      perm.append(nums[rank])
      nums.remove(nums[rank])
    # combine digits
    return "".join([str(digit) for digit in perm])

C++

class Solution {
public:
  /**
    * @param n: n
    * @param k: the kth permutation
    * @return: return the k-th permutation
    */
  string getPermutation(int n, int k) {
    // generate factorial list
    vector<int> factorial = vector<int>(n + 1, 1);
    for (int i = 1; i < n + 1; ++i) {
      factorial[i] = factorial[i - 1] * i;
    }
    // generate digits ranging from 1 to n
    vector<int> nums;
    for (int i = 1; i < n + 1; ++i) {
      nums.push_back(i);
    }

    vector<int> perm;
    for (int i = 0; i < n; ++i) {
      int rank = (k - 1) / factorial[n - i - 1];
      k = (k - 1) % factorial[n - i - 1] + 1;
      // append and remove nums[rank]
      perm.push_back(nums[rank]);
      nums.erase(std::remove(nums.begin(), nums.end(), nums[rank]), nums.end());
    }
    // transform a vector<int> to a string
    std::stringstream result;
    std::copy(perm.begin(), perm.end(), std::ostream_iterator<int>(result, ""));

    return result.str();
  }
};

Java

class Solution {
  /**
    * @param n: n
    * @param k: the kth permutation
    * @return: return the k-th permutation
    */
  public String getPermutation(int n, int k) {
    if (n <= 0 && k <= 0) return "";

    int fact = 1;
    // generate nums 1 to n
    List<Integer> nums = new ArrayList<Integer>();
    for (int i = 1; i <= n; i++) {
      fact *= i;
      nums.add(i);
    }

    // get the permutation digit
    StringBuilder sb = new StringBuilder();
    for (int i = n; i >= 1; i--) {
      fact /= i;
      // take care of rank and k
      int rank = (k - 1) / fact;
      k = (k - 1) % fact + 1;
      // ajust the mapping of rank to num
      sb.append(nums.get(rank));
      nums.remove(rank);
    }

    return sb.toString();
  }
}

源码分析

源码结构分为三步走，

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

复杂度分析

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

Reference

• Permutation Sequence 解题报告
• Permutation Sequence 参考程序 Java/C++/Python
• c++ - How to transform a vector into a string? - Stack Overflow