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

Question

从1到有n个人n。我必须写其产生的代码，并打印的所有不同的组合k，从这些人n。请解释用于此的算法。

Answer 1

我假设您是在询问组合意义上的组合（也就是说，元素的顺序无关紧要，所以[1 2 3]与相同[2 1 3]）。然后，这个想法非常简单，如果您了解归纳/递归：要获取所有K元素组合，请先从现有人员中选择组合的初始元素，然后将该初始元素与所有可能的组合“连接” K-1人们从继承最初元素的元素中产生出来。

举例来说，假设我们要从一组5个人中抽取3个人的所有组合。然后，可以用2个人的所有可能组合来表示3个人的所有可能组合：

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 ++代码：

#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 ]