计算n个数的全排列，输入n，输出1，2，3，...n的全排列，利用分治法实现。

分治法的基本思想是将问题分解成若干个小问题，然后将小问题的解合并起来得到原问题的解。对于全排列问题，可以采用以下分治法：

1. 将原序列分成两个子序列，分别计算它们的全排列。

2. 将两个子序列的全排列依次合并，得到原序列的全排列。

具体实现如下：

def permute(nums):
    if len(nums) <= 1:
        return [nums]
    res = []
    for i in range(len(nums)):
        rest = nums[:i] + nums[i+1:]
        for p in permute(rest):
            res.append([nums[i]] + p)
    return res

n = int(input("请输入n："))
nums = list(range(1, n+1))
print("全排列结果：")
result = permute(nums)
for r in result:
    print(r)

运行结果：

请输入n：4
全排列结果：
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]