python 3种算法 回溯法、字典序生成、递归交换 实现全排列【力扣46题】

输入: nums = [1,2,3]
输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

输入: nums = [0,1]
输出: [[0,1], [1,0]]

def permute(nums):
    """
    使用回溯算法生成数组的全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的全排列
    """
    def backtrack(path, options):
        # 如果当前路径的长度等于输入数组的长度，说明找到了一种排列
        if len(path) == len(nums):
            res.append(path[:])
            return
        
        # 遍历当前可选择的数字
        for i in range(len(options)):
            # 选择当前数字
            path.append(options[i])
            # 继续递归填下一个数
            backtrack(path, options[:i] + options[i+1:])
            # 撤销选择
            path.pop()
    res = []
    backtrack([], nums)
    return res
# 示例调用
print(permute([1, 2, 3]))  # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]

def permute(nums):
    """
    使用字典序算法生成数组的全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的全排列
    """
    def next_permutation(perm):
        # 找到升序的边界
        i = len(perm) - 2
        while i >= 0 and perm[i] >= perm[i + 1]:
            i -= 1
        if i == -1:
            return False
        
        # 找到需要交换的位置
        j = len(perm) - 1        while perm[j] <= perm[i]:
            j -= 1
        perm[i], perm[j] = perm[j], perm[i]
        
        # 反转i后面的部分
        perm[i + 1:] = perm[i + 1:][::-1]
        return True
    
    nums.sort()
    res = [nums[:]]
    while next_permutation(nums):
        res.append(nums[:])
    return res
# 示例调用
print(permute([1, 2, 3]))  # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]

def permute(nums):
    """
    使用递归交换方法生成数组的全排列
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的全排列
    """
    def backtrack(start):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    res = []
    backtrack(0)
    return res
# 示例调用
print(permute([1, 2, 3]))  # 输出: [[1, 2, 3], [1, 3, 2], ..., [3, 2, 1]]