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：此问题非常适合于记忆技术的应用.在此问题中,您可以创建一个地图并使用给定组合的矢量和填充它.在计算给定矢量集的总和之前,您可以查找是否已经计算了任何和的子集并使用这些结果.虽然您正在执行非常便宜且快速的求和,但如果您执行的计算要复杂得多且耗时,这种技术肯定会有助于带来一些重大的性能改进.