在 C++ 中创建 n 个项目的所有可能的 k 组合

2021-12-06 00:00:00 algorithm math combinations combinatorics c++

从1到n有n个人.我必须编写一个代码来生成和打印来自这些 n 的 k 人的所有不同组合.请解释用于此的算法.

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

推荐答案

我假设您在询问组合意义上的组合(即元素的顺序并不重要，所以 [1 2 3] 与 [2 1 3] 相同).这个想法很简单，如果你理解归纳/递归:要获得所有 K 元素组合，你首先从现有的一组人中选择组合的初始元素，然后你连接"这个初始元素与 K-1 人的所有可能组合是从初始元素之后的元素产生的.

I assume you're asking about combinations in combinatorial sense (that is, order of elements doesn't matter, so [1 2 3] is the same as [2 1 3]). The idea is pretty simple then, if you understand induction / recursion: to get all K-element combinations, you first pick initial element of a combination out of existing set of people, and then you "concatenate" this initial element with all possible combinations of K-1 people produced from elements that succeed the initial element.

举个例子，假设我们想从一组 5 人中取出 3 人的所有组合.那么3人的所有可能组合都可以用2人的所有可能组合来表示:

As an example, let's say we want to take all combinations of 3 people from a set of 5 people. Then all possible combinations of 3 people can be expressed in terms of all possible combinations of 2 people:

comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }

这是实现这个想法的 C++ 代码:

Here's C++ code that implements this idea:

#include <iostream>
#include <vector>

using namespace std;

vector<int> people;
vector<int> combination;

void pretty_print(const vector<int>& v) {
  static int count = 0;
  cout << "combination no " << (++count) << ": [ ";
  for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
  cout << "] " << endl;
}

void go(int offset, int k) {
  if (k == 0) {
    pretty_print(combination);
    return;
  }
  for (int i = offset; i <= people.size() - k; ++i) {
    combination.push_back(people[i]);
    go(i+1, k-1);
    combination.pop_back();
  }
}

int main() {
  int n = 5, k = 3;

  for (int i = 0; i < n; ++i) { people.push_back(i+1); }
  go(0, k);

  return 0;
}

这里是 N = 5, K = 3 的输出:

combination no 1:  [ 1 2 3 ] 
combination no 2:  [ 1 2 4 ] 
combination no 3:  [ 1 2 5 ] 
combination no 4:  [ 1 3 4 ] 
combination no 5:  [ 1 3 5 ] 
combination no 6:  [ 1 4 5 ] 
combination no 7:  [ 2 3 4 ] 
combination no 8:  [ 2 3 5 ] 
combination no 9:  [ 2 4 5 ] 
combination no 10: [ 3 4 5 ]

相关文章