n 个元素中 k 个元素的所有组合

all combinations of k elements out of n(n 个元素中 k 个元素的所有组合)

问题描述

有人可以给我一个函数的链接或伪代码，用于从 n 中找到 k 个元素的所有组合吗?可能在 STL 中.我不需要计算 n 选择 k，我需要列出所有大小为 k 的数字的向量.

Can somebody provide me a link or pseudocode of a function for finding all combinations of k elements out of n? possibly in STL. I don't need to compute n choose k, I need to list all vectors of numbers of size k.

谢谢

推荐答案

在 C++ 中给出以下例程:

In C++ given the following routine:

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;
}

然后您可以继续执行以下操作:

You can then proceed to do the following:

// 9-choose-3 
std::string s = "123456789";
std::size_t k = 3;
do
{
   std::cout << std::string(s.begin(),s.begin() + k) << std::endl;
}
while(next_combination(s.begin(),s.begin() + k,s.end()));

或者对于 int 的 std::vector:

Or for a std::vector of int's:

// 5-choose-3 
std::size_t n = 5;
std::size_t k = 3;

std::vector<int> ints;
for (int i = 0; i < n; ints.push_back(i++));

do
{
   for (int i = 0; i < k; ++i)
   {
      std::cout << ints[i];
   }
   std::cout << "
";
}
while(next_combination(ints.begin(),ints.begin() + k,ints.end()));

这篇关于n 个元素中 k 个元素的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！