在C中创建的n个元素的所有可能ķ组合++

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

有编号从1到N N人。我必须写其产生的code和打印ķ人民的所有不同组合的这n个。请解释一下使用该算法。

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] ）。我们的想法是pretty的简单的话，如果你了解诱导/递归：让所有的 K 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.

作为一个例子，假设我们要采取3人所有组合从一组5人。随后3人所有可能的组合可以pssed中的2人所有可能的组合而言EX $ P $：

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 ++ code实现这样的想法：

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 ]