有效地计算向量组合

有效地计算向量组合

在C ++中，给出以下例程：

template <typename Iterator>inline bool next_combination(const Iterator first,  Iterator k,       const Iterator last){      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

和

std::list

只是仅举几例。

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