Permutation

1. Next Permutation

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            self.swap(nums, i, j)
        self.reverse(nums, i + 1)

    def reverse(self, nums, start):
        i, j = start, len(nums) - 1
        while i < j:
            self.swap(nums, i, j)
            i += 1
            j -= 1

    def swap(self, nums, i, j):
        temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp

🧩 一、全排列基础题

46. Permutations

• 使用 回溯算法。

• 每一层选择一个未使用的元素加入路径。

• 当路径长度等于 len(nums) 时，将路径加入结果集。

class Solution:
    def permute(self, nums):
        res = []
        n = len(nums)
        def backtrack(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for num in nums:
                if num not in path:
                    path.append(num)
                    backtrack(path)
                    path.pop()
        backtrack([])
        return res

🔁 二、含重复元素的全排列

47. Permutations II

• 仍然是回溯，但要跳过重复分支。

• 排序后，如果当前元素和前一个相等，且前一个还未使用，则跳过。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        results = []

        def backtrack(comb, counter):
            if len(comb) == len(nums):
                # make a deep copy of the resulting permutation,
                # since the permutation would be backtracked later.
                results.append(list(comb))
                return

            for num in counter:
                if counter[num] > 0:
                    # add this number into the current combination
                    comb.append(num)
                    counter[num] -= 1
                    # continue the exploration
                    backtrack(comb, counter)
                    # revert the choice for the next exploration
                    comb.pop()
                    counter[num] += 1

        backtrack([], Counter(nums))

        return results

📈 三、下一个排列（字典序思路）

31. Next Permutation

1. 从右往左找第一个下降位置 i，满足 nums[i] < nums[i+1]。

2. 再从右往左找第一个比 nums[i] 大的元素 j。

3. 交换 nums[i] 与 nums[j]。

4. 反转 nums[i+1:]。

class Solution:
    def nextPermutation(self, nums):
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = reversed(nums[i + 1:])

🧮 四、第 k 个排列（数学法）

60. Permutation Sequence

• 利用 阶乘 计算每一位对应的数字。

• 第 i 位固定后剩下 n−i 位的排列数为 (n-i)!。

• 每次通过整除判断选哪个数字。

class Solution:
    def getPermutation(self, n, k):
        import math
        nums = [str(i) for i in range(1, n + 1)]
        k -= 1
        res = ""
        for i in range(n, 0, -1):
            fact = math.factorial(i - 1)
            idx = k // fact
            res += nums[idx]
            nums.pop(idx)
            k %= fact
        return res

🔡 五、字符串全排列（字母）

567. Permutation in String

• 滑动窗口 + 计数数组（或Counter）

• 窗口长度固定为 len(s1)

• 当窗口内计数与 s1 的计数相同 → True

from collections import Counter
class Solution:
    def checkInclusion(self, s1, s2):
        n, m = len(s1), len(s2)
        if n > m: return False
        c1, c2 = Counter(s1), Counter(s2[:n])
        if c1 == c2: return True
        for i in range(n, m):
            c2[s2[i]] += 1
            c2[s2[i-n]] -= 1
            if c2[s2[i-n]] == 0:
                del c2[s2[i-n]]
            if c1 == c2:
                return True
        return False

💡 六、其他排列相关题（拓展）

📚 七、总结比较