第k个排列

2021-01-11

要想解决本题，首先需要了解一个简单的结论：

对于 $n$ 个不同的元素（例如数 $1, 2, \cdots, n$），它们可以组成的排列总数目为 $n!$。

对于给定的 $n$ 和 $k$，我们不妨从左往右确定第 $k$ 个排列中的每一个位置上的元素到底是什么。

我们首先确定排列中的首个元素 $a_1$。根据上述的结论，我们可以知道：

以 $1$ 为 $a_1$的排列一共有 $(n-1)!$ 个；
以 $2$ 为 $a_1$的排列一共有 $(n-1)!$个；
$\cdots⋯$
以 $n$ 为 $a_1$的排列一共有 $(n-1)!$ 个。

由于我们需要求出从小到大的第 $k$ 个排列，因此：

如果 $k \leq (n-1)!$，我们就可以确定排列的首个元素为 $1$；
如果$(n-1)! < k \leq 2 \cdot (n-1)!$ ，我们就可以确定排列的首个元素为 2；
$\cdots⋯$
如果 $(n-1) \cdot (n-1)! < k \leq n \cdot (n-1)!$，我们就可以确定排列的首个元素为 $n$。
因此，第 $k$ 个排列的首个元素就是：

$a_1 = \lfloor \frac{k-1}{(n-1)!} \rfloor + 1$

其中 $\lfloor x \rfloor$ 表示将 $x$ 向下取整。

当我们确定了 $a_1$后，如何使用相似的思路，确定下一个元素 $a_2$呢？实际上，我们考虑以 $a_1$为首个元素的所有排列：

以 $[1,n] \backslash a_1$最小的元素为 $a_2$的排列一共有 $(n-2)!$个；
以 $[1,n] \backslash a_1$次小的元素为 $a_2$的排列一共有 $(n-2)!$个；
$\cdots⋯$
以 $[1,n] \backslash a_1$最大的元素为 $a_2$的排列一共有 $(n-2)!$个；

其中 $[1,n] \backslash a_1[1,n]$表示包含 $1, 2, \cdots n$ 中除去 $a_1$ 以外元素的集合。

这些排列从编号 $(a_1-1) \cdot (n-1)!$开始，到 $a_1 \cdot (n-1)!$结束，总计 $(n-1)!$个，因此第 $k$ 个排列实际上就对应着这其中的第$k’ = (k-1) \bmod (n-1)! + 1$个排列。这样一来，我们就把原问题转化成了一个完全相同但规模减少 1 的子问题：

求 $[1, n] \backslash a_1$这 $n-1$ 个元素组成的排列中，第 $k’$小的排列。
avatar

import java.util.Arrays;

public class Solution {

    /**
     * 记录数字是否使用过
     */
    private boolean[] used;

    /**
     * 阶乘数组
     */
    private int[] factorial;

    private int n;
    private int k;

    public String getPermutation(int n, int k) {
        this.n = n;
        this.k = k;
        calculateFactorial(n);

        // 查找全排列需要的布尔数组
        used = new boolean[n + 1];
        Arrays.fill(used, false);

        StringBuilder path = new StringBuilder();
        dfs(0, path);
        return path.toString();
    }


    /**
     * @param index 在这一步之前已经选择了几个数字，其值恰好等于这一步需要确定的下标位置
     * @param path
     */
    private void dfs(int index, StringBuilder path) {
        if (index == n) {
            return;
        }

        // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
        int cnt = factorial[n - 1 - index];
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (cnt < k) {
                k -= cnt;
                continue;
            }
            path.append(i);
            used[i] = true;
            dfs(index + 1, path);
            // 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
            // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
            return;
        }
    }

    /**
     * 计算阶乘数组
     *
     * @param n
     */
    private void calculateFactorial(int n) {
        factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
    }
}

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/di-kge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/hui-su-jian-zhi-python-dai-ma-java-dai-ma-by-liwei/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。