問題描述

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

這篇關于在 C++ 中創建 n 個項目的所有可能的 k 組合的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！