C++ 中的 std::views::cartesian_product

引言

C++ 中的 std::views::cartesian_product (C++23 中可用) 是 <ranges> 头文件下的范围库的一部分。它允许您生成多个范围的笛卡尔积，创建一个视图，该视图遍历这些范围中所有可能的元素组合。

std::views::cartesian_product 的目的

std::views::cartesian_product 提供了一种有效的方法来从多个输入范围生成笛卡尔积，而无需显式嵌套循环。它惰性操作，意味着实际的乘积是在您遍历视图时计算的，这使得它对于大型数据集来说内存效率很高。

语法和用法

要使用 std::views::cartesian_product，请包含 <ranges> 头文件。

让我们看看它如何以基本形式工作

实施

输出

 
Cartesian Product (range1 x range2):
(1, 5)
(1, 6)
(1, 7)
(2, 5)
(2, 6)
(2, 7)
(3, 5)
(3, 6)
(3, 7)
Filtered Cartesian Product (only even elements):
(2, 6)

说明

步骤 1：定义两个范围

程序首先定义两个数字范围。而不是使用更高级的 C++ 功能，范围是使用简单的列表（向量）创建的。第一个范围包含 {1, 2, 3} 等数字，第二个范围包含 {5, 6, 7} 等数字。这些范围是生成所有可能元素对的输入。

步骤 2：笛卡尔积计算

笛卡尔积是指生成第一个范围中的一个元素与第二个范围中的一个元素的所有组合。为了实现这一点，程序使用了两个嵌套循环。外层循环遍历第一个范围中的每个元素，对于第一个范围的每个组件，内层循环遍历第二个范围中的每个元素。这将创建所有可能的对（例如 (1, 5)、(1, 6)、(2, 5) 等）。当程序找到每个对时，它会将它们打印到屏幕上。

步骤 3：过滤乘积

生成笛卡尔积后，程序会应用一个条件来过滤掉特定的组合。在这种情况下，条件检查一对中的两个数字是否都是偶数。如果是，程序将打印该对。例如，如果第一个数字是 2，第二个数字是 6，它们都是偶数，因此该对将被显示。如果一个或两个数字是奇数，则该对将被跳过。

步骤 4：打印结果

随着循环的运行并找到所有对，程序将笛卡尔积打印到屏幕上，显示每对数字。然后，在应用过滤器后，它仅打印满足两个数字都是偶数条件的对。

复杂度分析

时间复杂度

笛卡尔积生成

• 程序使用两个嵌套循环来生成笛卡尔积。外层循环对第一个范围（假设其大小为 n）中的每个元素运行一次，内层循环对第二个范围（大小为 m）中的每个元素运行一次。
• 因此，总迭代次数为 n * m，这意味着生成笛卡尔积的时间复杂度为 O(n * m)。

过滤

• 在第二阶段，程序应用过滤条件（检查两个数字是否都是偶数）。此过滤是在迭代笛卡尔积时完成的。
• 过滤操作的时间复杂度也为 O(n * m)，因为它涉及在生成每个对时对其进行检查。

因此，程序的整体时间复杂度为 O(n * m)，其中 n 是第一个范围的大小，m 是第二个范围的大小。

空间复杂度

输入空间

• 程序使用两个向量（列表）来存储两个范围的元素。第一个向量有 n 个元素，第二个向量有 m 个元素。
• 因此，存储这些范围所需的空间为 O(n + m)。

笛卡尔积存储

• 由于程序在计算时生成和处理每个数字对，因此它不需要一次性存储所有对。笛卡尔积直接打印到屏幕（或经过过滤后打印），因此无需额外空间来存储整个结果。
• 因此，存储笛卡尔积本身的空间复杂度极小，因为一次只有一个对存储在内存中。这使得笛卡尔积部分的空间复杂度为 O(1)。

方法 1：递归笛卡尔积

递归方法通过一次遍历一个范围并递归地将结果与其他范围组合来生成多个范围（或列表）的笛卡尔积。此技术通过将问题分解为更小的子问题来消除对嵌套循环的需求。

实施

输出

 
{ 1 3 5 }
{ 1 3 6 }
{ 1 4 5 }
{ 1 4 6 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 4 5 }
{ 2 4 6 }   

说明

步骤 1：定义输入

程序以定义多个范围（或数字列表）开始。每个范围包含一组数字，目标是生成从每个范围中选择一个数字的所有可能组合。输入由分组的几个数字列表组成。

步骤 2：递归函数设置

递归函数是解决方案的核心部分。它接受三个输入

• 数字范围。
• 一个存储正在构建的当前组合的列表（或向量）。
• 一个深度参数，用于跟踪当前正在处理哪个范围。

深度从 0 开始，意味着函数首先处理第一个范围。随着递归的进行，它会深入到下一个范围，直到所有范围都被处理。

步骤 3：递归的基例

递归需要一个停止条件。当函数处理完所有范围时，就会发生基例。换句话说，当深度等于范围数量时，意味着已经形成了一个完整的组合。此时，该组合将被打印出来或返回。

步骤 4：递归情况（回溯）

在递归情况下，函数会遍历当前范围（基于深度）中的每个元素。对于每个元素，它会将该元素添加到当前组合中，然后进行递归调用以进入下一个范围（即增加深度）。

递归调用完成后，它会通过从当前组合中删除最后一个元素来“回溯”。这确保程序可以在没有先前选择干扰的情况下探索其他可能的组合。此回溯过程使程序能够系统地构建范围内的所有组合，而不会遗漏任何可能性。

步骤 5：构建和打印组合

随着递归的深入，程序通过从每个范围添加一个元素来构建一个组合。一旦达到基例（所有范围都已处理），函数就会打印当前组合。打印后，它会回溯以探索其余的可能性。

示例

想象一下有三个范围，如 {1, 2}、{3, 4} 和 {5, 6}。递归函数首先从第一个范围中选择 1，然后调用自身来处理第二个范围，选择 3，最后处理第三个范围，选择 5。这就形成了组合 (1, 3, 5)。一旦完成，它就会回溯，删除 5，然后尝试 6 来创建组合 (1, 3, 6)。所有范围中的所有元素都会发生相同的过程，以确保生成所有可能的组合。

步骤 6：完成

递归将继续进行，直到从每个范围中选择一个元素的所有可能组合都被打印出来。通过使用递归和回溯，代码可以在不需要复杂循环的情况下有效地探索所有组合。

复杂度分析

时间复杂度

对于递归方法，时间复杂度取决于范围的数量和每个范围的大小

笛卡尔积生成

• 如果有 k 个范围，平均每个范围包含 n 个元素，则通过笛卡尔积生成的组合（或对）的总数是所有范围大小的乘积。
• 这意味着生成的组合总数将与 O(n^k) 成正比，其中 n 是范围的平均大小，k 是范围的数量。
• 由于函数将每个组合打印一次，因此生成和打印所有组合的时间复杂度为 O(n^k)。

递归函数调用

• 递归函数将为生成的每个组合调用一次，这意味着它也将被调用 O(n^k) 次，因为每次调用都处理一个组合。

因此，递归方法的整体时间复杂度为 O(n^k)。

空间复杂度

输入存储

• 输入由 k 个范围组成，每个范围的平均大小为 n。因此，存储这些范围需要 O(k * n) 的空间。

递归栈

• 在任何时候，递归深度都对应于范围的数量 k。在最坏的情况下，递归函数将在达到基例之前调用自身 k 次。因此，递归栈的最大深度为 O(k)。

组合的临时存储

• 当前正在构建的组合存储在一个临时向量（current）中。该向量的大小与 k 成正比，因为它存储了每个范围的一个元素。
• 因此，存储当前组合所需的空间为 O(k)。

由于组合被立即打印或处理，而无需在内存中存储，因此不需要额外的空间来同时存储所有组合。

因此，整体空间复杂度为 O(k * n)，主要由输入大小和递归深度决定。

性质

1. 可扩展性

处理多个范围：递归方法可以处理任意数量的范围，无论您有两个范围还是几十个范围。这种灵活性使其具有高度的可扩展性。像嵌套循环这样的传统解决方案，当范围数量增加时，会变得越来越复杂且难以管理。相比之下，递归保持了解决方案的简单性，因为递归深度会随着范围数量的增加而自然增加。函数无需重写；它可以处理任意数量的输入范围，只需调整递归深度即可。

动态输入：由于递归不依赖于显式定义的循环，因此它可以适应运行时动态确定范围数量的情况。此属性在输入数据未提前固定的场景中很重要，例如处理用户提供的数据或配置时。

2. 回溯效率

内存效率：回溯确保探索每个组合，而不会不必要地保留不再属于当前组合的元素。一旦算法探索了一条路径，它就会立即通过从当前组合中删除最近的方面来回溯。这确保算法不会存储冗余或不必要的数据。

有效探索：回溯是一项强大的技术，因为它能够系统地探索所有可能性而无需重复工作。通过“撤销”先前的选择并探索替代路径，递归方法可以有效地生成所有可能的组合，而无需将所有组合都存储在内存中。

3. 动态范围处理

适应动态输入：与需要程序员定义需要多少循环的硬编码循环不同，递归可以适应动态输入大小。您可以轻松修改输入范围的数量（或其内容），而无需更改 函数 的核心逻辑。这使得解决方案高度适应输入可能频繁更改的场景，例如在用户可配置软件中。

处理任意数据：递归可以处理不仅大小不同，内容也可能不同的范围（例如 字符串、对象 或其他 数据类型）。您可以插入不同类型的范围而无需修改算法，这使得该方法对于各种应用程序都非常通用，例如在不同域中生成所有可能的配置或组合。