Python递归生成全排列序列实操

下面就是Python递归生成全排列序列的完整攻略。

什么是全排列

全排列是指对给定的n个元素进行排列，n个元素的所有排列情况共有n!种，即从n个元素中任取不重复元素进行排列的所有情况。

例如，给定元素为[1,2,3]，它们的全排列情况如下所示：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

实现递归生成全排列

要实现递归生成全排列序列，我们可以采用交换元素的方法，在将某个元素固定在第一位的情况下，递归生成剩余元素的全排列序列。下面是Python代码实现：

def permute(nums, index):
    """
    递归生成全排列序列
    :param nums: 元素列表
    :param index: 当前固定元素的索引
    """
    if index == len(nums) - 1:  # 固定最后一个元素，得到一个排列
        print(nums)
        return
    for i in range(index, len(nums)):  # 将当前固定的元素与后面的元素依次交换
        nums[index], nums[i] = nums[i], nums[index]
        permute(nums, index + 1)
        nums[index], nums[i] = nums[i], nums[index]  # 恢复原列表，便于交换元素

在上面的代码中，我们通过递归调用permute()函数，在每次固定一个元素后，对余下的元素进行全排列。在将元素交换前，我们先交换元素后再交换。这是为了保证回溯到上一层调用时，列表元素的顺序不会发生改变。

例如，对于元素列表[1,2,3]，我们初始时将第1个元素固定，生成全排列序列的代码如下：

nums = [1, 2, 3]
permute(nums, 0)

运行结果如下所示：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

Python递归生成指定长度的全排列

有时候，我们不需要生成所有元素的全排列，而只需要生成指定长度的元素全排列，这时我们可以在递归函数中增加一个参数，表示生成的排列长度。下面是Python代码实现：

def permute_length(nums, index, length):
    """
    递归生成指定长度的全排列序列
    :param nums: 元素列表
    :param index: 当前固定元素的索引
    :param length: 生成的排列长度
    """
    if index == length - 1:  # 固定最后一个元素，得到一个排列
        print(nums[:length])
        return
    for i in range(index, len(nums)):  # 将当前固定的元素与后面的元素依次交换
        nums[index], nums[i] = nums[i], nums[index]
        permute_length(nums, index + 1, length)
        nums[index], nums[i] = nums[i], nums[index]  # 恢复原列表，便于交换元素

例如，对于元素列表[1,2,3,4]，我们固定第1个元素，生成长度为3的全排列序列的代码如下：

nums = [1, 2, 3, 4]
permute_length(nums, 0, 3)

运行结果如下所示：

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 3]
[1, 4, 2]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 3]
[2, 4, 1]
[3, 2, 1]
[3, 2, 4]
[3, 1, 2]
[3, 1, 4]
[3, 4, 1]
[3, 4, 2]
[4, 2, 3]
[4, 2, 1]
[4, 3, 2]
[4, 3, 1]
[4, 1, 3]
[4, 1, 2]

至此，Python递归生成全排列序列实操攻略完整结束。