Python 找到直到N的所有可能的唯一大小为K的组合

在许多编程场景中，我们经常遇到需要从给定的元素集合中找到特定大小的所有可能组合的需求。这些组合在各种应用中非常有用，例如生成排列组合、解决组合问题或探索数据的不同子集。在本博客文章中，我们将探讨一种有效的方法来使用Python编程语言找到直到给定数字N的大小为K的所有唯一组合。

理解问题

在我们深入解决方案之前，让我们明确定义我们要解决的问题。给定一个从1到N的数字范围和一个期望的组合大小K，我们的目标是生成从给定范围中的K个数字的所有可能唯一组合。

例如，假设我们有N = 5和K = 3。预期输出将是-

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

方法和算法

创建一个空的结果列表来存储组合。

result = []

定义一个递归函数backtrack，接受以下参数：start和current_combination。

def backtrack(start, current_combination):
   # ... code for the recursive function ...

如果current_combination的长度等于K，将其添加到结果列表中并返回。

if len(current_combination) == k:
   result.append(current_combination)
   return

从start迭代到N −
- 将当前数字添加到current_combination。
- 递归调用递归函数，将start增加1。
- 从current_combination中删除最后一个元素，以回溯和探索其他可能性。

for i in range(start, n + 1):
    backtrack(i + 1, current_combination + [i])

首先将回溯函数调用，并将start设置为1，current_combination设置为空。

backtrack(1, [])

处理无效输入

为了确保我们解决方案的健壮性，我们可以添加一些输入验证检查。例如，我们可以检查给定的N值是否大于或等于K。如果不是，我们可以引发异常或返回一个空列表，表示从比K小的范围中无法形成大小为K的组合。

def combinations(n, k):
   if n < k:
      raise ValueError("Invalid input: N must be greater than or equal to K.")

   # ...

优化算法

当前的实现通过探索递归树的所有分支来生成所有可能的组合。然而，如果所需的组合大小K相对于范围N比较小，我们可以通过修剪某些分支来优化算法。例如，如果剩余可选择的数字不足以形成大小为K的组合，我们可以停止探索该分支。

def combinations(n, k):
   # ... existing code ...

   def backtrack(start, current_combination):
      if len(current_combination) == k:
         result.append(current_combination)
         return

      # Optimization: Check if remaining numbers are enough for a valid combination
      if k - len(current_combination) > n - start + 1:
         return

      for i in range(start, n + 1):
         backtrack(i + 1, current_combination + [i])

   # ...

这种优化可以减少不必要的计算，并且可以显著提高算法在较大的N和K值下的性能。

无效输入的示例输出

让我们考虑一个无效输入的示例，以展示对这类情况的处理。

输入

combinations(2, 4)
try:
   print(combinations(2, 4))
except ValueError as e:
   print(e)

输出

Invalid input: N must be greater than or equal to K.

在这种情况下，我们引发了一个 ValueError来表明输入无效，因为范围 (2) 小于所需的组合大小 (4)。

在Python中实现解决方案

下面是解决方案的完整实现−

def combinations(n, k):
   result = []

   def backtrack(start, current_combination):
      if len(current_combination) == k:
         result.append(current_combination)
         return

      for i in range(start, n + 1):
         backtrack(i + 1, current_combination + [i])

   backtrack(1, [])
   return result

测试解决方案

让我们用一些示例输入来测试解决方案 −

示例

print(combinations(5, 3))

输出

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

示例

print(combinations(4, 2))

输出

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

解释

让我们详细分析第一个例子−

输入：combinations（5，3）

初始时，结果为空列表。
调用回溯函数，start = 1，current_combination = []。
在循环的第一次迭代（i = 1）中，我们将1添加到current_combination并对backtrack（2，[1]）进行递归调用。
在循环的第一次迭代（i = 2）中，我们将2添加到current_combination并对backtrack（3，[1, 2]）进行递归调用。
由于[1, 2]的长度等于3（K），我们将其添加到结果中。
回溯到之前的状态，我们从current_combination中删除最后一个元素以探索其他可能性（[1]）。
在循环的第二次迭代（i = 3）中，我们将3添加到current_combination并对backtrack（4，[1, 3]）进行递归调用。
由于[1, 3]的长度等于3（K），我们将其添加到结果中。
回溯到之前的状态，我们从current_combination中删除最后一个元素以探索其他可能性（[1]）。
我们继续这个过程直到生成所有可能的组合。
最终的结果是[[1, 2, 3]，[1, 2, 4]，[1, 2, 5]，[1, 3, 4]，[1, 3, 5]，[1, 4, 5]，[2, 3 , 4]，[2, 3, 5]，[2, 4, 5]，[3, 4, 5]]，它代表了从1到5的数字中大小为3的所有唯一组合。