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 kth permutation sequence.

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

分析

首先可以想到一个简单直白的方法,即调用 k-1next_permutation(),从而得到第k个排列。这个方法把前k个排列全部求出来了,比较浪费,时间复杂度是 O(kn),所以会超时。有没有办法直接求第k个排列呢?有!

利用康托编码的思路,假设有n个不重复的元素,第k个排列是a1,a2,a3,...,ana_1, a_2, a_3, …, a_n,那么a1a_1是哪一个位置呢?

我们把a1a_1去掉,那么剩下的排列为a2,a3,...,ana_2, a_3, …, a_n, 共计n-1个元素,n-1个元素共有(n-1)!个排列,于是就可以知道 a1=k/(n1)!a_1 = k / (n-1)!

同理,a2,a3,...,ana_2, a_3, …, a_n 的值推导如下:

k2=k%(n1)!k_2 = k\%(n-1)!

a2=k2/(n2)!a_2 = k_2/(n-2)!

\quad \cdots

kn1=kn2%2!k{n-1} = k{n-2}\%2!

an1=kn1/1!a{n-1} = k{n-1}/1!

an=0a_n = 0

康托编码

  1. // Permutation Sequence
  2. // 康托编码
  3. // 时间复杂度O(n),空间复杂度O(1)
  4. public class Solution {
  5. public String getPermutation(int n, int k) {
  6. string s(n, '0');
  7. string result;
  8. for (int i = 0; i < n; ++i)
  9. s[i] += i + 1;
  10. return kth_permutation(s, k);
  11. }
  12. private:
  13. int factorial(int n) {
  14. int result = 1;
  15. for (int i = 1; i < n+1; ++i)
  16. result *= i;
  17. return result;
  18. }
  19. // s 已排好序,是第一个排列
  20. string kth_permutation(string &s, int k) {
  21. const int n = s.size();
  22. string result;
  23. int base = factorial(n - 1);
  24. --k; // 康托编码从0开始
  25. for (int i = n - 1; i > 0; k %= base, base /= i, --i) {
  26. auto a = next(s.begin(), k / base);
  27. result.push_back(*a);
  28. s.erase(a);
  29. }
  30. result.push_back(s[0]); // 最后一个
  31. return result;
  32. }
  33. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/permutation-sequence.html