高效计算向量组合

出于好奇，我正在研究一个研究问题，但我不知道如何对我想到的逻辑进行编程。让我向你解释一下：

我有四个向量，例如，

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.：我正在尝试研究数据挖掘中先验算法的修改版本。

在 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 例程的面向迭代器的接口，任何STL也可以使用支持通过迭代器向前迭代的容器，例如std::vector, std::deque and std::list仅举几个。

Note 2:这个问题非常适合记忆技术的应用。在此问题中，您可以创建一个映射并用给定组合的向量和填充它。在计算给定向量集的总和之前，您可以查找是否已计算总和的任何子集并使用这些结果。尽管您执行的求和非常便宜且快速，但如果您执行的计算要复杂得多且耗时得多，则此技术肯定会有助于带来一些重大的性能改进。