寻找第 k 个排列

题目描述

给定两个数字 $n$ 和 $k$，求 $n$ 的第 $k$ 个排列。当 $n = 3$ 时，所有排列（按顺序）如下：

示例输入

此处 4 是数字 $n$，8 是要求的第 $k$ 个排列的序号。

14, 8

期望输出

12143

我们需要找到第 $k$ 个排列。

自行尝试

多标签代码

C++

1#include <string>
2#include <vector>
3#include <iostream>
4
5using namespace std;
6
7string GetPermutation(int n, int k) {
8	//TODO: 写你的代码
9	return "-1";
10}

Java

1// 导入所需函数
2import java.util.*;
3
4class KthPermutation {
5	static String getPermutation(int n, int k) {
6		// TODO: 写你的代码
7		return "-1";
8	}
9}

Python

1import math
2
3def get_permutation(v, k):
4  # TODO: 写你的代码
5  return -1

JS

1let getPermutation = function(n, k) {
2  // TODO: 写你的代码
3  return -1;
4};

Ruby

1def get_permutation(n, k)
2   # TODO: 写你的代码
3  return -1
4end

Go

1package main
2import (
3	"fmt"
4	"encoding/json"
5	/* 测试时取消注释以下库 */
6	// "strconv"
7	// "strings"
8)
9
10func GetPermutation(n int, k int) string {
11	// TODO: 写你的代码
12	return "-1"
13}

解法

首先讨论一些基本概念。我们知道 $n!$ 是大小为 $n$ 的集合的全排列总数。另一个明显且重要的概念是：如果我们为第一个位置选择一个元素，则剩余元素的排列数为 $(n-1)!$。

例如，若给定元素 {1, 2, 3, 4}，我们选择 1 作为第一个元素，则剩余元素的排列如下：

其数量为 6，即 $(n-1)!$。无论我们为首位选择哪个元素，这个数值都相同。

暴力解法：

• 一种寻找第 $k$ 个排列的朴素方法是生成所有排列，然后返回第 $k$ 个。
• 另一种说法是维护一个已遍历排列的计数器，当达到第 $k$ 个时返回。

优化解法：

• 如果仔细观察上图，我们可以做得更好。如果我们知道 $k$ 所在的“块”，就能确定第一个元素。
• 同理，在该块内，如果能确定 $k$ 所在的子块，就能确定第二个元素。可以递归地进行此过程，直到没有可选元素为止。以下是 $k = 8$ 时的可视化表示：

以下是采用的算法：

1如果输入向量为空，则返回结果向量
2
3block_size = (n-1)! [n 是向量的大小]
4确定 k 所在的块，并选取该块的第一个元素
5（可通过 (k-1)/block_size 计算）
6
7将选中的元素添加到结果向量中，并从原输入向量中移除
8
9从 k 中减去跳过的块数，即 k = k - selected * block_size，重复步骤 1

下面以 $k = 8$ 为例逐步说明：

多标签代码

C++

1#include <string>
2#include <vector>
3#include <iostream>
4
5using namespace std;
6
7int factorial(int n) {
8	if (n == 0 || n == 1) return 1;
9	return n * factorial(n - 1);
10}
11
12void FindKthPermutation(vector<char>& v, int k, string& result,
13						vector<int>& factorial) {
14	if (v.empty()) {
15		return;
16	}
17
18	int n = (int)(v.size());
19
20	// factorial 是以第一个数字开头的排列数
21	// selected 是当前排列中已选数字的数量
22	int selected = (k - 1) / factorial[n - 1];
23
24	// 获取选定数组中的第一个数字
25	result += v[selected];
26	v.erase(v.begin() + selected);
27	k = k - (factorial[n - 1] * selected);
28
29	// 递归调用自身
30	FindKthPermutation(v, k, result, factorial);
31}
32
33string GetPermutation(int n, int k) {
34	vector<char> v;
35
36	// 构造排列数字
37	char c = '1';
38	for (char i = 1; i <= n; ++i) {
39		v.push_back(c);
40		c++;
41	}
42
43	vector<int> factorial;
44	for (int i = 0; i < n; i++) {
45		if (i == 0 || i == 1) {
46			factorial.push_back(1);
47		} else {
48			factorial.push_back(i * factorial[i - 1]);
49		}
50	}
51
52	string result = "";
53	FindKthPermutation(v, k, result, factorial);
54	return result;
55}
56
57int main() {
58	cout << "1. 12 的第 2 个排列 = " << GetPermutation(2, 2) << endl;
59	cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
60	cout << "2. 123 的第 5 个排列 = " << GetPermutation(3, 5) << endl;
61	cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
62	cout << "3. 1234 的第 8 个排列 = " << GetPermutation(4, 8) << endl;
63}

Java

1// 导入所需函数
2import java.util.*;
3
4class KthPermutation {
5	static void findKthPermutation(List<Character> v, int k, StringBuilder result,
6			List<Integer> factorial) {
7		if (v.isEmpty()) {
8			return;
9		}
10		int n = v.size();
11
12		// factorial 是以第一个数字开头的排列数
13		// selected 是当前排列中已选数字的数量
14		int selected = (k - 1) / factorial.get(n - 1);
15
16		// 获取选定数组中的第一个数字
17		result.append(v.get(selected));
18		v.remove(selected);
19		k = k - (factorial.get(n - 1) * selected);
20
21		// 递归调用自身
22		findKthPermutation(v, k, result, factorial);
23	}
24
25	static String getPermutation(int n, int k) {
26		List<Character> v = new ArrayList<Character>();
27
28		// 构造排列数字
29		char c = '1';
30		for (int i = 1; i <= n; i++) {
31			v.add(c);
32			c++;
33		}
34
35		// 计算阶乘并存储
36		List<Integer> factorial = new ArrayList<Integer>();
37		for (int i = 0; i < n; i++) {
38			if (i == 0 || i == 1) {
39				factorial.add(1);
40			} else {
41				factorial.add(i * factorial.get(i - 1));
42			}
43		}
44
45		StringBuilder result = new StringBuilder();
46		findKthPermutation(v, k, result, factorial);
47		return result.toString();
48	}
49
50	public static void main(String[] args) {
51		System.out.println("1. 12 的第 2 个排列 = " + getPermutation(2, 2));
52		System.out.println( "\n------------------------------------------------------------------------------------------------------\n");
53		System.out.println("2. 123 的第 5 个排列 = " + getPermutation(3, 5));
54		System.out.println("\n------------------------------------------------------------------------------------------------------\n");
55		System.out.println("3. 1234 的第 8 个排列 = " + getPermutation(4, 8));
56	}
57}

Python

1import math
2
3def find_kth_permutation(v, k, result, factorial):
4    if not v:
5        return
6
7    n = len(v)
8
9    # factorial 是以第一个数字开头的排列数
10    # selected 是当前排列中已选数字的数量
11    selected = (k - 1) // factorial[n - 1]
12
13    # 获取选定数组中的第一个数字
14    result += str(v[selected])
15    del v[selected]
16    k = k - (factorial[n - 1] * selected)
17
18    # 递归调用自身
19    find_kth_permutation(v, k, result, factorial)
20
21
22def get_permutation(n, k):
23    v = list(range(1, n + 1))
24    block_size = []
25    for i in range(n):
26        block_size.append(math.factorial(i))
27
28    result = []
29    find_kth_permutation(v, k, result, block_size)
30    return ''.join(result)
31
32
33def main():
34    print("1. 12 的第 2 个排列 =", get_permutation(2, 2))
35    print("\n------------------------------------------------------------------------------------------------------\n")
36    print("2. 123 的第 5 个排列 =", get_permutation(3, 5))
37    print("\n------------------------------------------------------------------------------------------------------\n")
38    print("3. 1234 的第 8 个排列 =", get_permutation(4, 8))
39
40
41if __name__ == '__main__':
42    main()

JS

1let findKthPermutation = function(v, k, result, factorial) {
2    if (!v || v.length == 0) {
3      return;
4    }
5    let n = v.length;
6    // factorial 是以第一个数字开头的排列数
7    // selected 是当前排列中已选数字的数量
8    let selected = Math.floor((k - 1) / factorial[n-1]);
9    
10    // 获取选定数组中的第一个数字
11    result[0] += '' + v[selected];
12    v.splice(selected, 1);
13    k = k - (factorial[n-1] * selected);
14
15    // 递归调用自身
16    findKthPermutation(v, k, result, factorial);
17};
18
19let getPermutation = function(n, k) {
20    let v = [];
21    // 构造排列数字
22    for (let i = 0; i < n; i++) {
23      v.push(i + 1);
24    }
25
26    // 计算阶乘并存入 block size
27    let blockSize = [];
28    for(let i=0;i<n;i++){
29      if (i == 0 || i == 1) {
30        blockSize.push(1);
31      } else {
32        blockSize.push(i * blockSize[i-1]);
33      }
34    }
35
36    let result = [''];
37    findKthPermutation(v, k, result, blockSize);
38    return result[0];
39};
40
41console.log("1. 12 的第 2 个排列 =", getPermutation(2, 2));
42console.log( "\n------------------------------------------------------------------------------------------------------\n");
43console.log("2. 123 的第 5 个排列 =", getPermutation(3, 5));
44console.log( "\n------------------------------------------------------------------------------------------------------\n");
45console.log("3. 1234 的第 8 个排列 =", getPermutation(4, 8));

Ruby

1def find_kth_permutation(v, k, result, factorial)
2    return if !v or v.length == 0
3    n = v.length
4    
5    # factorial 是以第一个数字开头的排列数
6    # selected 是当前排列中已选数字的数量
7    selected = ((k - 1) / factorial[n - 1]).floor
8    
9    # 获取选定数组中的第一个数字
10    result.push(v[selected])
11    v.delete_at(selected)
12    k = k - (factorial[n - 1] * selected)
13
14    # 递归调用自身
15    find_kth_permutation(v, k, result, factorial)
16end
17
18# 工具函数用于计算阶乘
19def factorial_utility(n)
20    return 1 if n == 0 || n == 1 
21    return n * factorial_utility(n - 1)
22end
23  
24def get_permutation(n, k)
25    v = []
26    
27    # 构造排列数字
28    for i in 1..n
29        v.push(i.to_s) 
30    end
31
32    # 计算阶乘并存入 block_size
33    block_size = []
34    n.times { |i| block_size.push(factorial_utility(i)) }
35
36    result = []
37    find_kth_permutation(v, k, result, block_size)
38    return result.join("")
39end
40
41# 主程序
42puts("1. 12 的第 2 个排列 = " + get_permutation(2, 2).to_s)
43puts( "------------------------------------------------------------------------------------------------------\n")
44puts("2. 123 的第 5 个排列 = " + get_permutation(3, 5).to_s)
45puts( "------------------------------------------------------------------------------------------------------\n")
46puts("3. 1234 的第 8 个排列 = " + get_permutation(4, 8).to_s)

Go

1package main
2
3import (
4	"fmt"
5	"strconv"
6	"strings"
7)
8/* FindKthPermutation 是一个辅助函数，用于递归查找第 k 个排列。 */
9func FindKthPermutation(v []int, k int, result *[]string, factorial []int) {
10	if len(v) == 0 { return }
11
12	n := len(v)
13
14	// factorial 是以第一个数字开头的排列数
15	// selected 是当前排列中已选数字的数量
16	selected := (k - 1) / factorial[n - 1]
17
18	// 获取选定数组中的第一个数字
19	*result = append(*result, strconv.Itoa(v[selected]))
20	v = append(v[:selected], v[selected+1:]...)
21	k = k - (factorial[n-1] * selected)
22
23	// 递归调用自身
24	FindKthPermutation(v, k, result, factorial)
25}
26/* GetPermutation 是一个函数，使用 FindKthPermutation 辅助函数来生成排列 */
27func GetPermutation(n int, k int) string {
28
29	v := make([]int, n)
30	// 构造排列数字
31	for i := 0; i < n; i++ {
32		v[i] = i + 1
33	}
34
35	factorial := make([]int, n)
36	factorial[0] = 1
37	// 计算阶乘并存储
38	for i := 1; i < n; i++ {
39		factorial[i] = factorial[i-1] * i
40	}
41
42	result := make([]string, 0)
43	FindKthPermutation(v, k, &result, factorial)
44	return strings.Join(result, "")
45}
46
47func main() {
48	fmt.Print("1. 12 的第 2 个排列 = ", GetPermutation(2, 2))
49	fmt.Print("\n------------------------------------------------------------------------------------------------------\n")
50	fmt.Print("2. 123 的第 5 个排列 = ", GetPermutation(3, 5))
51	fmt.Print("\n------------------------------------------------------------------------------------------------------\n")
52	fmt.Print("3. 1234 的第 8 个排列 = ", GetPermutation(4, 8))
53}

时间复杂度

该解法的时间复杂度为 $O(n^2)$，因为每步从数组中删除元素需要线性时间。

空间复杂度

该解法的空间复杂度为线性，$O(n)$。