迭代列表列表的笛卡尔积

Question

该问题是以下简单问题的概括：

给定 3 个元素列表，我可以通过伪代码循环遍历所有 3 个列表之间的配对：

foreach( element1 in list1 )
    foreach( element2 in list2 )
        foreach( element3 in list3 )
            dosomething( element1, element2, element3 )

因此，它将每个列表中的一个元素与其他列表中的每个元素组合配对。

现在我有一个元素列表的列表，所以有 N 个列表。我怎样才能做到同样的原理？

到目前为止，我最好的办法是计算每个配对的索引，并迭代以这种方式计算的索引：

假设与每个列表的第一个元素的配对的索引为 0。为了说明这一点，我们将其称为

{0,0,0,...}

。下一个索引 (1) 将是

{1,0,0,...}

。如果第一个列表有

size0

元素，则配对

{0,1,0,...}

将获得索引

size0

。配对

{2,4,1,0,...}

将获得索引

(1*size1 + 4*size0 + 2)

。

有更好的方法吗？有内置此功能的语言吗？目前我需要 C++ 中的它，但通用解决方案是这个问题的答案。具体语言的实现可以在评论中留下。

Answer 1

使用递归

#include <iostream>
#include <vector>

template <typename T>
void cartesian_product_helper(const std::vector<std::vector<T>>& lists, std::vector<T>& current_product, size_t depth) {
    if (depth == lists.size()) {
        for (const T& element : current_product) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    } else {
        for (const T& element : lists[depth]) {
            current_product.push_back(element);
            cartesian_product_helper(lists, current_product, depth + 1);
            current_product.pop_back();
        }
    }
}

template <typename T>
void cartesian_product(const std::vector<std::vector<T>>& lists) {
    std::vector<T> current_product;
    cartesian_product_helper(lists, current_product, 0);
}

int main() {
    std::vector<std::vector<int>> lists = {{1, 2}, {3, 4}, {5, 6}};
    cartesian_product(lists);
    return 0;
}