Python第k個排列怎么實現

本篇內容介紹了“Python第k個排列怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目

給出集合 [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個排列怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！