第k个排列

题目

给出集合[1,2,3,…,n]，其所有元素共有n!种排列。

按大小顺序列出所有排列情况，并一一标记，当n = 3时, 所有排列如下：

"123"

"132"

"213"

"231"

"312"

"321"

给定n和k，返回第k个排列。

说明：

给定n的范围是[1,9]。

给定k的范围是[1,n!]。

非固定进制法

我们可以将按大小顺序列出的所有排序视为非固定进制的整数。固定进制的整数，比如十进制整数，

每一位都在0, 1, 2, 3, 4, 5, 6, 7, 8, 9之中循环
假设位数为 $n$ ，第 $k$ 个十进制整数中，第一位（从左往右数）的值为 $\frac{k \mod 10^{n}}{10^{10-1}}$ ，第 $x$ （ $0 \leq x < n$ ，从0开始计）位止值为 $\frac{k \mod 10^{n-x}}{10^{n-1-x}}$

排列的特点是，每一位的取值范围是不同的。假设是 $n$ 个元素排列，第一位的取值范围是 $n$ 个，第二位的取值范围是 $n-1$ 个，第三位的取值范围是 $n-2$ ，依此类推。

所以，将 $n$ 个元素所有排序按大小顺序列出，第 $k$ 个排序中，第 $x$ 位的值为 $\frac{k \mod (n-x)!}{(n-1-x)!}$ 。

代码实现

package io.github.rscai.leetcode.bytedance.array; import java.util.LinkedList; import java.util.List; public class Solution1021A { public String getPermutation(int n, int k) { int[] indexes = new int[n]; // 0-based index for (int i = 0; i < indexes.length; i++) { indexes[i] = ((k - 1) % factorial(n - i)) / factorial(n - 1 - i); } List<String> chars = new LinkedList<>(); for (int i = 1; i <= n; i++) { chars.add(String.valueOf(i)); } StringBuilder result = new StringBuilder(); for (int index : indexes) { result.append(chars.get(index)); chars.remove(index); } return result.toString(); } private int factorial(int n) { if (n == 0) { return 1; } return n * factorial(n - 1); } }

首先，按着公式 $f(x) = \frac{k \mod (n-x)!}{(n-1-x)!}$ 计算每一位值的索引。

然后，获取每一位上的值。因为每一位上的候选值列表都不相同，而且受前面位上取值影响。所以，每决定一位的值，都要将其从候选列表中移除。

阶乘则以递归实现。

复杂度分析

时间复杂度

本演算法针对每一位都计算了两次阶乘。然后，遍历了每一位两次。时间复杂度为：

$\begin{aligned} C_{time} &= \sum_{i=0}^{n-1}(C_{time}(factorial(n-i)) + C_{time}(factorial(n-1-i))) + n + n \\ &= \frac{n(n+1)}{2} + \frac{n(n+1)}{2} + 2n \\ &= n^{2}+n + 2n \\ &= \mathcal{O}(n^{2}) \end{aligned}$

空间复杂度

使用了三个长度为 $n$ 的列表。空间复杂度为：

$\begin{aligned} C_{space} &= n + n+ n \\ &=\mathcal{O}(n) \end{aligned}$

动态规划法

上述演算法时间复杂度发生在计算阶乘。阶乘是以递归实现的，将阶乘的递归以树的形式展现：

可以发现有很多子树是重复的，这意味着「有重复的子问题」，以以使用「动态规划」优化。

动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、电脑科学、经济学和生物资讯学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最佳子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化储存，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

概述

动态规划在寻找有很多重叠子问题的情况的最佳解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被储存，从简单的问题直到整个问题都被解决。因此，动态规划储存递回时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最佳子结构的问题。最佳子结构的意思是局部最佳解能决定全域最佳解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

适用情况

最佳子结构性质。如果问题的最佳解所包含的子问题的解也是最佳的，我们就称该问题具有最佳子结构性质（即满足最佳化原理）。最佳子结构性质为动态规划演算法解决问题提供了重要线索。

无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

子问题重叠性质。子问题重叠性质是指在用递回演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划演算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果储存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地检视一下结果，从而获得较高的效率。

参考

动态规划

Dynamic Programming

代码实现

package io.github.rscai.leetcode.bytedance.array; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.function.Function; public class Solution1021B { public String getPermutation(int n, int k) { Function<Integer, Integer> factorial = new Function<Integer, Integer>() { private Map<Integer, Integer> cachedSolutions = new HashMap<>(); @Override public Integer apply(Integer n) { if (cachedSolutions.containsKey(n)) { return cachedSolutions.get(n); } Integer solution = doApply(n); cachedSolutions.put(n, solution); return solution; } private int doApply(int n) { if (n == 0) { return 1; } return n * apply(n - 1); } }; int[] indexes = new int[n]; // 0-based index for (int i = 0; i < indexes.length; i++) { indexes[i] = ((k - 1) % factorial.apply(n - i)) / factorial.apply(n - 1 - i); } List<String> chars = new LinkedList<>(); for (int i = 1; i <= n; i++) { chars.add(String.valueOf(i)); } StringBuilder result = new StringBuilder(); for (int index : indexes) { result.append(chars.get(index)); chars.remove(index); } return result.toString(); } }

首先，一样地按着公式 $f(x) = \frac{k \mod (n-x)!}{(n-1-x)!}$ 计算每一位值的索引。

然后，获取每一位上的值。因为每一位上的候选值列表都不相同，而且受前面位上取值影响。所以，每决定一位的值，都要将其从候选列表中移除。

阶乘使用函数式实现，该函数使用HashMap存储函数值，从而实现「动态规划」避免重复计算。