获得笛卡尔积的算法 [英] Algorithm to get Cartesian product
本文介绍了获得笛卡尔积的算法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我有一个像 [0,2,3,0,1]
这样的数组作为输入,我需要找到 { 0} x {0,1,2} x {0,1,2,3} x {0} x {0,1}
,更确切地说,我需要输出如下。
I have an array like [0,2,3,0,1]
as input , and I need to find Cartesian product of {0}x{0,1,2}x{0,1,2,3}x{0}x{0,1}
, more precisely I need to have output as following.
输入:
[0, 2, 3, 0, 1]
输出:
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1]
[0, 0, 1, 0, 0]
[0, 0, 1, 0, 1]
[0, 0, 2, 0, 0]
[0, 0, 2, 0, 1]
[0, 0, 3, 0, 0]
[0, 0, 3, 0, 1]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 1]
[0, 1, 1, 0, 0]
[0, 1, 1, 0, 1]
[0, 1, 2, 0, 0]
[0, 1, 2, 0, 1]
[0, 1, 3, 0, 0]
[0, 1, 3, 0, 1]
[0, 2, 0, 0, 0]
[0, 2, 0, 0, 1]
[0, 2, 1, 0, 0]
[0, 2, 1, 0, 1]
[0, 2, 2, 0, 0]
[0, 2, 2, 0, 1]
[0, 2, 3, 0, 0]
[0, 2, 3, 0, 1]
我需要一个通用算法。任何的想法 ?我想用C ++编写。
谢谢
I need a general algorithm. Any idea ? I would like to write it in c++. Thanks
推荐答案
一个硬代码解决方案是:
A hard code solution would be:
for (int a1 : {0}) {
for (int a2 : {0,1,2}) {
for (int a3 : {0,1,2,3}) {
for (int a4 : {0}) {
for (int a5 : {0,1}) {
do_job(a1, a2, a3, a4, a5);
}
}
}
}
}
您可以使用以下通用方法(将所有 a
放入向量):
You may use the following for a generic way (putting all a
s into vector):
bool increase(const std::vector<std::size_t>& v, std::vector<std::size_t>& it)
{
for (std::size_t i = 0, size = it.size(); i != size; ++i) {
const std::size_t index = size - 1 - i;
++it[index];
if (it[index] > v[index]) {
it[index] = 0;
} else {
return true;
}
}
return false;
}
void iterate(const std::vector<std::size_t>& v)
{
std::vector<std::size_t> it(v.size(), 0);
do {
do_job(it);
} while (increase(v, it));
}
这篇关于获得笛卡尔积的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文