建站
咨詢
售后
建站咨詢
新聞中心
本篇內(nèi)容介紹了“Python第k個(gè)排列怎么實(shí)現(xiàn)”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
成都創(chuàng)新互聯(lián)是一家專注于做網(wǎng)站、成都網(wǎng)站制作與策劃設(shè)計(jì),建德網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計(jì)領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:建德等地區(qū)。建德做網(wǎng)站價(jià)格咨詢:18982081108
題目
給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。
按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng) n = 3 時(shí), 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
給定 n 和 k，返回第 k 個(gè)排列。
說明：
給定 n 的范圍是 [1, 9]。
給定 k 的范圍是[1, n!]。
示例 1:
輸入: n = 3, k = 3 輸出: "213"
示例 2:
輸入: n = 4, k = 9 輸出: "2314"
解題思路
思路：DFS + 剪枝
先審題，題目中說明，給定集合 [1, 2, 3, ..., n] 有 n! 中排列。按大小順序列出所有排列情況，進(jìn)行標(biāo)記，然后返回第 k 個(gè)排列。
那么按照題意，我們最容易想到的就是列出 [1, 2, 3 ..., n] 個(gè)元素全排列，然后返回第 k 個(gè)排列，但是這樣效率可能會(huì)非常低，而且我們也沒有必要去求得所有的全排列。
在這里我們可以先看看規(guī)律，題目中開始就說了，按照大小順序列出所有排列情況。也就說，n 個(gè)元素組合的數(shù)，這個(gè)數(shù)每個(gè)元素都是從小到大進(jìn)行選擇的。例如示例 1：
輸入：n = 3, k = 3
在這里，給定的 n 為 3，那么要組合的數(shù)為 3 位數(shù)。這里它的全排列情況如下：
"123"
"132"
"213"
"231"
"312"
"321"
我們可以發(fā)現(xiàn)，第一個(gè)元素是從 1 開始選擇，逐漸增大。當(dāng)首元素確定之后，第二個(gè)元素同樣是從小到大選擇的，例如 123，132 。
根據(jù)上面的分析，我們可以發(fā)現(xiàn)，假設(shè)給定 n 個(gè)元素，
當(dāng)確定首元素時(shí)，后面元素則有 (n-1)! 中排列組合數(shù)，也就意味著首元素選擇后，當(dāng)前分支會(huì)產(chǎn)生 (n-1)! 種排列數(shù)。以此類推，當(dāng)確定前面兩個(gè)元素時(shí)，后面能產(chǎn)生的排列數(shù)則為 (n-2)!。那么：
當(dāng) k 大于前面分支能夠產(chǎn)生的排列數(shù)時(shí)，我們可以直接跳過；
當(dāng) k 小于或等于當(dāng)前分支產(chǎn)生的排列數(shù)時(shí)，也就說明要找的答案在這個(gè)分支的某個(gè)排列中，這個(gè)時(shí)候，我們遞歸去求解（確定逐個(gè)元素）。
具體的代碼如下。
class Solution: def getPermutation(self, n: int, k: int) -> str: # 階乘數(shù)組 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: 排列元素選擇數(shù)組 """ cnt = len(tmp) if cnt == n: return ''.join(tmp) # 排列數(shù)， # 這里注意，剛開始排列數(shù)組中元素個(gè)數(shù) cnt 為 0， # 此時(shí)要開始添加元素，所以要去除當(dāng)前元素，計(jì)算后續(xù)的排列數(shù)， # 所以排列數(shù)為 (n-cnt-1)!，對應(yīng) arr[n-cnt-1] arr_num = arr[n-cnt-1] # 比較 k 與當(dāng)前分支的排列數(shù) for i in range(1, n+1): if used[i]: continue if k > arr_num: # 剪枝 # 如果 k 大于當(dāng)前分支排列數(shù)，更新 k，跳過當(dāng)前分支 k -= arr_num continue # 否則，將當(dāng)前數(shù)添加到排列中 tmp.append(str(i)) used[i] = True # 繼續(xù)向下選擇 return dfs(k, tmp) return dfs(k, [])
“Python第k個(gè)排列怎么實(shí)現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
分享標(biāo)題：Python第k個(gè)排列怎么實(shí)現(xiàn)
URL鏈接：http://www.dlmjj.cn/article/gegdoo.html
