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

本文介绍了在 C++ 中创建 n 个项目的所有可能的 k 组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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