LeetCode 排列序列：康托展開逆向構造第 k 個排列

---

題目描述

給定 n 和 k，返回由 [1,2,...,n] 組成的所有排列中第 k 個（1-indexed）。

範例：

輸入: n = 3, k = 3
全排列: "123", "132", "213", "231", "312", "321"
輸出: "213"

解題思路：階乘數制（康托展開）確定每位

n 個數共有 n! 個排列。首位確定時，剩餘 (n-1)! 種可能。因此：

1. 預計算階乘 factorial = (n-1)!
2. k-- 轉為 0-indexed
3. 第 i 位索引：index = k / factorial
4. 從可用數字列表中取出 index 位置的數
5. k %= factorial，factorial /= (n-i-1) 進入下一位

時間複雜度：O(n²)（列表刪除 O(n)），空間複雜度：O(n)。

Python 參考實現

class Solution:
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        k -= 1  # 0-indexed
        factorial = 1
        for i in range(1, n):
            factorial *= i  # (n-1)!
        
        numbers = list(range(1, n + 1))
        result = []
        
        for i in range(n - 1, 0, -1):
            index = k // factorial
            result.append(str(numbers[index]))
            numbers.pop(index)
            k %= factorial
            factorial //= i
        
        result.append(str(numbers[0]))
        return ''.join(result)

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.getPermutation(3, 3) == "213"
    assert sol.getPermutation(9, 324) == "123685974"
    assert sol.getPermutation(1, 1) == "1"
    print("所有測試通過")

核心要點總結

• 康托展開逆用：正向是排列→序號，逆向是序號→排列
• 階乘數制：每位權重為 (剩餘長度-1)!
• k-- 關鍵：題目 1-indexed，算法需 0-indexed
• 列表操作：pop(index) 取出並刪除，保持剩餘有序

排列序列是組合數學在算法中的直接應用，掌握「階乘數制定位」思想，可解決「第 k 個組合/排列/子集」等系列問題。