Python第k个排列怎么实现
本篇内容介绍了“Python第k个排列怎么实现”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
成都创新互联是一家专注于做网站、成都网站制作与策划设计,建德网站建设哪家好?成都创新互联做网站,专注于网站建设十多年,网设计领域的专业建站公司;建站业务涵盖:建德等地区。建德做网站价格咨询:18982081108
题目
给出集合 [1,2,3,…,n]
,其所有元素共有 n!
种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3
时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 n
和 k
,返回第 k
个排列。
说明:
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3 输出: "213"
示例 2:
输入: n = 4, k = 9 输出: "2314"
解题思路
思路:DFS + 剪枝
先审题,题目中说明,给定集合 [1, 2, 3, ..., n]
有 n!
中排列。按大小顺序列出所有排列情况,进行标记,然后返回第 k 个排列。
那么按照题意,我们最容易想到的就是列出 [1, 2, 3 ..., n]
个元素全排列,然后返回第 k 个排列,但是这样效率可能会非常低,而且我们也没有必要去求得所有的全排列。
在这里我们可以先看看规律,题目中开始就说了,按照大小顺序列出所有排列情况。也就说,n 个元素组合的数,这个数每个元素都是从小到大进行选择的。例如示例 1:
输入:n = 3, k = 3
在这里,给定的 n 为 3,那么要组合的数为 3 位数。这里它的全排列情况如下:
"123"
"132"
"213"
"231"
"312"
"321"
我们可以发现,第一个元素是从 1 开始选择,逐渐增大。当首元素确定之后,第二个元素同样是从小到大选择的,例如 123
,132
。
根据上面的分析,我们可以发现,假设给定 n 个元素,
当确定首元素时,后面元素则有 (n-1)!
中排列组合数,也就意味着首元素选择后,当前分支会产生 (n-1)!
种排列数。以此类推,当确定前面两个元素时,后面能产生的排列数则为 (n-2)!
。那么:
当 k 大于前面分支能够产生的排列数时,我们可以直接跳过;
当 k 小于或等于当前分支产生的排列数时,也就说明要找的答案在这个分支的某个排列中,这个时候,我们递归去求解(确定逐个元素)。
具体的代码如下。
class Solution: def getPermutation(self, n: int, k: int) -> str: # 阶乘数组 arr = [1 for _ in range(n+1)] for i in range(2, n+1): arr[i] = arr[i-1] * i used = [False for _ in range(n+1)] def dfs(k, tmp): """ Args: tmp: 排列元素选择数组 """ cnt = len(tmp) if cnt == n: return ''.join(tmp) # 排列数, # 这里注意,刚开始排列数组中元素个数 cnt 为 0, # 此时要开始添加元素,所以要去除当前元素,计算后续的排列数, # 所以排列数为 (n-cnt-1)!,对应 arr[n-cnt-1] arr_num = arr[n-cnt-1] # 比较 k 与当前分支的排列数 for i in range(1, n+1): if used[i]: continue if k > arr_num: # 剪枝 # 如果 k 大于当前分支排列数,更新 k,跳过当前分支 k -= arr_num continue # 否则,将当前数添加到排列中 tmp.append(str(i)) used[i] = True # 继续向下选择 return dfs(k, tmp) return dfs(k, [])
“Python第k个排列怎么实现”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站,小编将为大家输出更多高质量的实用文章!
分享标题:Python第k个排列怎么实现
本文URL:http://pwwzsj.com/article/gegdoo.html