出于好奇,我正在研究一个研究问题,但我不知道如何对我想到的逻辑进行编程。让我向您解释一下:
我有四个 vector ,例如,
v1 = 1 1 1 1
v2 = 2 2 2 2
v3 = 3 3 3 3
v4 = 4 4 4 4
现在我要做的是组合添加它们,也就是
v12 = v1+v2
v13 = v1+v3
v14 = v1+v4
v23 = v2+v3
v24 = v2+v4
v34 = v3+v4
到这一步就好了。现在的问题是我想为这些 vector 中的每一个添加一个来自 v1、v2、v3、v4 的 vector ,它以前没有添加过。例如:
v3 和 v4 还没有添加到 v12,所以我想创建 v123 和 v124。同样,对于所有 vector ,
v12 should become:
v123 = v12+v3
v124 = v12+v4
v13 should become:
v132 // This should not occur because I already have v123
v134
v14 should become:
v142 // Cannot occur because I've v124 already
v143 // Cannot occur
v23 should become:
v231 // Cannot occur
v234 ... and so on.
重要的是我不要在一开始就一步一步做所有的事情。例如,我可以做(4 选择 3)4C3 并完成它,但我想在每次迭代时逐步完成。
我该如何编程?
P.S.:我正在尝试研究数据挖掘中先验算法的修改版本。
最佳答案
在 C++ 中,给定以下例程:
template <typename Iterator>
inline bool next_combination(const Iterator first,
Iterator k,
const Iterator last)
{
/* Credits: Thomas Draper */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
然后您可以继续执行以下操作:
int main()
{
unsigned int vec_idx[] = {0,1,2,3,4};
const std::size_t vec_idx_size = sizeof(vec_idx) / sizeof(unsigned int);
{
// All unique combinations of two vectors, for example, 5C2
std::size_t k = 2;
do
{
std::cout << "Vector Indicies: ";
for (std::size_t i = 0; i < k; ++i)
{
std::cout << vec_idx[i] << " ";
}
}
while (next_combination(vec_idx,
vec_idx + k,
vec_idx + vec_idx_size));
}
std::sort(vec_idx,vec_idx + vec_idx_size);
{
// All unique combinations of three vectors, for example, 5C3
std::size_t k = 3;
do
{
std::cout << "Vector Indicies: ";
for (std::size_t i = 0; i < k; ++i)
{
std::cout << vec_idx[i] << " ";
}
}
while (next_combination(vec_idx,
vec_idx + k,
vec_idx + vec_idx_size));
}
return 0;
}
**注 1:* 由于 next_combination 例程的面向迭代器的接口(interface),任何 STL也可以使用通过迭代器支持前向迭代的容器,例如 std::vector
、std::deque
和 std::list
仅举几例。
注2:这个问题很适合memoization技术的应用。在这个问题中,您可以创建一个 map 并用给定组合的 vector 和填充它。在计算一组给定 vector 的总和之前,您可以查找以查看是否已经计算了总和的任何子集并使用这些结果。尽管您执行的求和非常便宜且快速,但如果您执行的计算要复杂得多且耗时得多,则此技术肯定有助于带来一些重大的性能改进。
关于c++ - 高效计算 vector 组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4590075/