出于好奇,我正在研究一个研究问题,我不知道如何编写我想到的逻辑.让我向你解释一下：
我有四个载体,例如,
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
直到这一步它很好.现在的问题是我想要从v1,v2,v3,v4中添加这些向量中的每一个,它之前没有添加过.例如：
v3和v4尚未添加到v12,因此我想创建v123和v124.类似地,对于所有的矢量,
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.：我正在尝试在数据挖掘中研究apriori算法的修改版本.
解决方法
在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,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 + vec_idx_size));
}
return 0;
}
**注1：*由于next_combination例程的面向迭代器的接口,也可以使用任何通过迭代器支持前向迭代的STL容器,例如std :: vector,std :: deque和std :: list一些.
注2：此问题非常适合于记忆技术的应用.在此问题中,您可以创建一个地图并使用给定组合的矢量和填充它.在计算给定矢量集的总和之前,您可以查找是否已经计算了任何和的子集并使用这些结果.虽然您正在执行非常便宜且快速的求和,但如果您执行的计算要复杂得多且耗时,这种技术肯定会有助于带来一些重大的性能改进.
