从n个元素中选取k个元素的所有组合

Question

有人能提供一个函数的链接或伪代码，用于在n个元素中找到所有k个元素的组合吗？最好使用STL。我不需要计算n个选择k, 我需要列出所有大小为k的数字向量。

谢谢

- Bob

---

“我不需要计算n选k，我需要列出所有大小为k的数字向量。”的意思是什么？无论如何，编写一个“next_combination”函数都很简单。参考链接：https://dev59.com/MnE95IYBdhLWcg3wp_yn#2616837。 - James McNellis

你尝试过自己做吗？听起来你是在让我们帮你做功课。 - prolink007

我建议将此移至http://programmers.stackexchange.com/。 - Andrei Duma

@Andrei，我认为这是算法导向的，因此更适合在这里讨论。Programmers.stackexchange可能会像“我的团队中没有人理解组合数学，我们该如何进行教育？” - corsiKa

可能是如何迭代遍历n张扑克牌的每一种可能的组合的重复问题。 - Mike Seymour

Answer 1

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

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

// 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：

// 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 << "\n";
}
while(next_combination(ints.begin(),ints.begin() + k,ints.end()));

- Matthieu N.

---

你能提供一些关于你的代码如何工作的直觉吗？我试图跟随逻辑，但老实说我没有任何理由相信它会起作用。 - templatetypedef

如果你打印出第一个例子中的整个字符串，你可以看到算法是如何操作的。该字符串在任何时候都包含两个已排序的部分。 - UncleBens

值得注意的是，当k等于零时，do...while是不正确的，因为此时不应生成任何组合。 - Alexander Kjäll

那段代码由于未使用的赋值和修改itr1而存在某种错误： itr1 = last; --itr1; itr1 = k; - ThreeBit

Answer 2

http://howardhinnant.github.io/combinations.html

搜索 "for_each_combination"。如果您找到更快的算法，请告诉我。与我经常看到的其他算法不同，这个算法不需要元素类型是LessThanComparable。

- Howard Hinnant

---

像往常一样，您的库非常棒。谢谢。如果在循环中加入std::execution::par，我们不会介意哦。[眨眼] - scx

Answer 3

创建一个辅助向量，其中有n-k个零和k个一。0表示原始容器中的元素未被包含，而1表示该元素已被包含。现在，在辅助向量上使用std::next_permutation获取下一个组合。

- user515430

Answer 4

这里是一个懒惰的伪代码示例，可以完成工作...

void nChooseK(array[n],k){
    recurse("",array[n],k);      
}

void recurse(initialString,array[n],k){
    if(k == 0){
        print initialString;
        return;
     }
    for(i=0;i<n;i++){
        tmpArray = array[0...i-1]+array[i+1...];//the array without the object to remove
        recurse(initialString + array[i], tmpArray,k-1)
    }        
}

- nosirrahcd

---

从技术上讲，您正在生成每个子集 k! 次。如果将“tmpArray”创建为“array[i+1,...]”，则每个可能的集合只会生成一次。 - Pablo

太好了，Pablo。没错。 - nosirrahcd

Answer 5

你可以使用std::next_permutation，但它是n！而不是n选k。你可以在创建它们后对它们进行过滤。但这个解决方案是O(n!)，并不是非常完美。这里是试错解决方案：

int factorial(int value)
{
    int result = 1;

    for(int i = 1; i <= value; i++)
    {
        result *= i;
    }

    return result;
}

std::set<std::set<int>> binomial_coefficient(std::vector<int> input, int k)
{
    std::set<std::set<int>> solutions;

    for(unsigned int i = 0; i < factorial(input.size()); i++)
    {
        std::next_permutation(input.begin(), input.end());

        solutions.insert(std::set<int>(input.begin(), input.begin() + k));
    }

    return solutions;
}

- Fox32

---

通过将算法减速n!倍比“不是真正完美”更糟糕。对于任何合理的n值，这意味着它在宇宙毁灭之前都无法完成。尽管在这种情况下，阶乘函数将简单地溢出int范围并产生垃圾。 - Mike Seymour