Python递归实现排列组合问题

2023-04-15 00:00:00 python 递归排列组合

先来看一下排列和组合的定义：

排列：从N个不同元素中取出M个元素，且要求其按照一定顺序排列的情况，称为从N个元素中取出M个元素的排列，记作 A(N,M) 或者 P(N,M)，读作“N取M的排列”

组合：从N个不同元素中取出M个元素，且不要求其按照一定顺序排列的情况，称为从N个元素中取出M个元素的组合，记作 C(N,M)，读作“N取M的组合”

那么如何用递归去实现这些问题呢？以排列问题为例：

假设我们有一个列表 nums 和一个整数 k，我们需要从 nums 中取出 k 个元素排列，输出所有可能的排列。

首先我们可以定义一个递归函数 recursion(nums, result, path, k)，它接收四个参数：

nums：原始列表，即从中取出元素的列表
result：存储结果的列表，即所有可能的排列
path：存储当前正在组合的元素的列表
k：需要取出的元素个数

我们可以考虑从 nums 中取出一个元素，将它添加到 path 中，然后递归调用 recursion 函数，继续从剩下的元素中取出一个元素，直到 path 中元素的个数达到 k。此时将 path 加入到 result 中即为一个排列。

具体实现如下：

def recursion(nums, result, path, k):
    if len(path) == k:  # 如果 path 中元素个数达到 k，加入到结果列表中
        result.append(path)
        return
    for i in range(len(nums)):
        recursion(nums[:i] + nums[i+1:], result, path + [nums[i]], k)  # 从剩余的数组中递归选择下一个元素

def permutation(nums, k):
    result = []
    recursion(nums, result, [], k)
    return result

接下来，我们来看看如何实现组合问题：

假设我们有一个列表 nums 和一个整数 k，我们需要从 nums 中取出 k 个元素组合，输出所有可能的组合。

同样，我们可以定义一个递归函数 recursion(nums, result, path, k, start)，它接受五个参数：

nums：原始列表，即从中取出元素的列表
result：存储结果的列表，即所有可能的组合
path：存储当前正在组合的元素的列表
k：需要取出的元素个数
start：下一个元素应该从哪里开始选取

我们可以考虑从 nums 中的 start 位置开始选取一个元素，将它添加到 path 中，然后递归调用 recursion 函数，继续从 start+1 位置开始选取一个元素，直到 path 中元素的个数达到 k。此时将 path 加入到 result 中即为一个组合。

具体实现如下：

def recursion(nums, result, path, k, start):
    if len(path) == k:  # 如果 path 中元素个数达到 k，加入到结果列表中
        result.append(path)
        return
    for i in range(start, len(nums)):
        recursion(nums, result, path + [nums[i]], k, i+1)  # 从 i+1 位置开始选取下一个元素

def combination(nums, k):
    result = []
    recursion(nums, result, [], k, 0)
    return result

运行下列程序进行测试：

nums = [1, 2, 3, 4]
k = 2
print(permutation(nums, k))
print(combination(nums, k))

输出结果如下：

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

可以看到，我们成功地实现了排列和组合问题的递归解法。

相关文章