#include <iostream>
#include <vector>
void cartesian (std::vector<std::vector<int>> const& items) {
auto n = items.size();
auto next = [&](std::vector<int> & x) {
for ( int i = 0; i < n; ++ i )
if ( ++x[i] == items[i].size() ) x[i] = 0;
else return true;
return false;
};
auto print = [&](std::vector<int> const& x) {
for ( int i = 0; i < n; ++ i )
std::cout << items[i][x[i]] << ",";
std::cout << "\b \n";
};
std::vector<int> x(n);
do print(x); while (next(x));
}
int main () {
std::vector<std::vector<int>>
items { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } };
cartesian(items);
return 0;
}
这背后的想法如下。
令 n := items.size()。
对于所有 i 属于 {0,1,...,n-1}，令 m_i := items[i].size()。
令 M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1}。
我们首先解决更简单的问题，即遍历 M。这可以通过 next lambda 实现。该算法只是小学生用来加 1 的“进位”例程，尽管使用了混合基数数字系统。
我们使用此方法通过公式 items[i][x[i]]（其中 i 属于 {0,1,...,n-1}）将元组 x 转换为所需的元组之一。我们在 print lambda 中执行此转换。
然后，我们使用 do print(x); while (next(x)); 进行迭代。
现在对复杂度进行一些评论，假设对于所有的i，m_i > 1：
- 该算法需要
O(n)的空间。请注意，显式构造笛卡尔积需要O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n)的空间。因此，这比任何需要同时在内存中存储所有元组的算法在空间上更具指数级的优势。
next函数的平摊时间为O(1)（通过几何级数论证）。print函数需要O(n)的时间。- 因此，总体而言，该算法的时间复杂度为
O(n|M|)，空间复杂度为O(n)（不计算存储items的成本）。
一个有趣的事情要注意的是，如果将
print替换为一个函数，该函数平均只检查每个元组中的
O(1)个坐标而不是所有坐标，则时间复杂度降至
O(|M|)，也就是说，它随着笛卡尔积大小的增加呈线性增长。换句话说，在某些情况下避免每次迭代都复制元组可能是有意义的。
