遍历列表列表的笛卡尔积

Iterating over the cartesian product of a list of lists

提问人:Daniel Bauer 提问时间:9/14/2023 最后编辑:Daniel Bauer 更新时间:9/15/2023 访问量:47

问:

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

给定 3 个元素列表,我可以通过 foling 伪代码来遍历所有 3 个列表之间的配对:

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

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

现在我有一个元素列表列表,所以有 N 个列表。我怎样才能做到同样的原则?

到目前为止,我最好的办法是为每个配对计算一个指数,并迭代以这种方式计算的指数:

假设与每个列表的第一个元素配对获得索引 0。为了说明这一点,我们称之为 .下一个索引 (1) 将是 。如果第一个列表有元素,则配对将获得索引 。配对将获得索引 。{0,0,0,...}{1,0,0,...}size0{0,1,0,...}size0{2,4,1,0,...}(1*size1 + 4*size0 + 2)

有没有更好的方法?是否有内置此功能的语言?目前我在C++中需要它,但通用解决方案是这个问题的答案。特定于语言的实现可以保留在注释中。

算法 可扩展性 组合学 笛卡尔积

评论

1赞 Nico Haase 9/14/2023
这可能取决于您的数据结构,但为什么不使用递归呢?
1赞 trincot 9/14/2023
这称为笛卡尔积。
0赞 Daniel Bauer 9/14/2023
同时,我使用递归实现了它。如果您@Nico Haase,想要发布解决方案,可以详细说明如何操作。否则,我会在几天内自己发布答案。

答:

2赞 arpan.r 9/15/2023 #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;
}
1赞 Matt Timmermans 9/15/2023 #2

您可以像用小数一样进行计数,只是每个数字的基数是相应列表的长度:

vector<size_t>: sizes, indexes;
vector<T>: elements;

foreach (auto list: lists) {
    sizes.push_back(list.size());
    indexes.push_back(0);
    elements.push_back(list[0]);
}

int digit = 0;
do {
    doSomething(elements);

    for (digit = (int)indexes.size()-1; digit>=0; --digit) {
        if (++(indexes[digit]) >= sizes[digit]) {
            // carry
            indexes[digit] = 0;
            elements[digit] = lists[digit][0];
        } else {
            elements[digit] = lists[digit][indexes[digit]];
            break;
        }
    }
} while(digit>=0);