组合算法

8.1 组合算法的定义。

组合算法是用于解决与计数、列举和生成各种组合结构相关问题的算法。 这些算法用于处理集合、子集、排列、组合和其他组合对象。

组合问题的主要类型

• 排列: 集合元素的所有可能有序组合。
• 组合: 给定大小的所有可能无序子集。
• 布置: 给定大小的所有可能有序子集。
• 划分: 将集合划分为子集的所有可能方法。
• 组合对象: 其他结构，如图、矩阵等。

组合算法的优缺点

优点：

• 完整列举: 这些算法可以列举所有可能的组合，这对于穷举搜索非常有用。
• 灵活性: 它们可以适应解决与组合学相关的广泛问题。
• 直观性: 许多算法因递归方法和回溯技术（backtracking）而易于理解和实现。

缺点：

• 组合爆炸: 随着输入数据规模的增长，执行时间和内存量可能急剧增加（例如，O(n!)）。
• 非最优性: 在组合量大时，这些算法可能效率不高，需要优化或替代更先进的技术（例如，使用动态规划或贪心算法）。

组合算法的时间和空间复杂度

时间复杂度：

• 排列: O(n!)，其中n是集合的元素数量。
• 组合: O(C(n, k))，其中C(n, k)是二项式系数，等于n! / (k! * (n - k)!)。
• 布置: O(A(n, k))，其中A(n, k)是布置数量，等于n! / (n - k)!。
• 子集: O(2^n)，因为每个n个元素都可以被包括或不包括在子集中。

空间复杂度：

通常是O(n)用于存储递归构建过程中的中间结果，但最终内存可能需要用于存储所有结果（例如，排列的O(n * n!)）。

组合算法示例

8.2 生成排列。

任务:

查找给定集合元素的所有唯一排列。

算法:

使用递归或迭代方法生成元素的所有可能有序组合。

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        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]

    backtrack(0)
    return result

print(permute([1, 2, 3]))

8.3 生成组合

任务:

查找集合中给定大小的所有组合。

算法:

使用递归或迭代方法生成给定大小的所有可能子集。

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

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
        

8.4 生成集合划分

任务:

查找将集合分割成子集的所有可能方法。

算法:

使用递归方法生成集合的所有可能划分。

import copy

def partition_set(s):
    result = []

    def backtrack(part, rest):
        if not rest:
            result.append(copy.deepcopy(part[:]))
            return
        for i in range(len(part)):
            part[i].append(rest[0])
            backtrack(part, rest[1:])
            part[i].pop()
        part.append([rest[0]])
        backtrack(part, rest[1:])
        part.pop()

    backtrack([], list(s))
    return result

print(partition_set({1, 2, 3}))
        
        

使用 copy.deepcopy(part[:]) 创建列表 part 的深拷贝。这意味着创建了一个新的、独立的列表，该列表与原始 part 无关。 这样，result 中的每个元素都将代表一个唯一的划分。