Python第k個(gè)排列怎么實(shí)現(xiàn)

本篇內(nèi)容介紹了“Python第k個(gè)排列怎么實(shí)現(xiàn)”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(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è)排列。

說(shuō)明：

  • 給定 n 的范圍是 [1, 9]。

  • 給定 k 的范圍是[1, n!]。

示例 1:

輸入: n = 3, k = 3
輸出: "213"

示例 2:

輸入: n = 4, k = 9
輸出: "2314"

解題思路

思路：DFS + 剪枝

先審題，題目中說(shuō)明，給定集合 [1, 2, 3, ..., n] 有 n! 中排列。按大小順序列出所有排列情況，進(jìn)行標(biāo)記，然后返回第 k 個(gè)排列。

那么按照題意，我們最容易想到的就是列出 [1, 2, 3 ..., n] 個(gè)元素全排列，然后返回第 k 個(gè)排列，但是這樣效率可能會(huì)非常低，而且我們也沒(méi)有必要去求得所有的全排列。

在這里我們可以先看看規(guī)律，題目中開(kāi)始就說(shuō)了，按照大小順序列出所有排列情況。也就說(shuō)，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 開(kāi)始選擇，逐漸增大。當(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í)，我們可以直接跳過(guò)；

  • 當(dāng) k 小于或等于當(dāng)前分支產(chǎn)生的排列數(shù)時(shí)，也就說(shuō)明要找的答案在這個(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ù)，
            # 這里注意，剛開(kāi)始排列數(shù)組中元素個(gè)數(shù) cnt 為 0，
            # 此時(shí)要開(kāi)始添加元素，所以要去除當(dāng)前元素，計(jì)算后續(xù)的排列數(shù)，
            # 所以排列數(shù)為 (n-cnt-1)!，對(duì)應(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，跳過(guò)當(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)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

名稱欄目：Python第k個(gè)排列怎么實(shí)現(xiàn)
文章分享：http://bm7419.com/article0/gegdoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、品牌網(wǎng)站設(shè)計(jì)、虛擬主機(jī)、企業(yè)網(wǎng)站制作、網(wǎng)站建設(shè)、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司