在c ++中生成组合

我一直在寻找一个使用c ++来生成组合的源代码。 我发现了一些高级的代码,但是这只适用于特定数量的预定义数据。 任何人都可以给我一些提示,或者也许有一些想法来产生组合。 作为一个例子,假设集合S = {1,2,3,…,n},我们从中选取r = 2。 input将是nr 。在这种情况下,程序将生成长度为2的数组,如5 2个输出1 2,1 3等。我很难构buildalgorithm。 我花了一个月的时间思考这个问题。

一个简单的方法使用std::next_permutation

 #include <iostream> #include <algorithm> #include <vector> int main() { int n, r; std::cin >> n; std::cin >> r; std::vector<bool> v(n); std::fill(v.end() - r, v.end(), true); do { for (int i = 0; i < n; ++i) { if (v[i]) { std::cout << (i + 1) << " "; } } std::cout << "\n"; } while (std::next_permutation(v.begin(), v.end())); return 0; } 

或者输出结果的轻微变化更容易遵循顺序:

 #include <iostream> #include <algorithm> #include <vector> int main() { int n, r; std::cin >> n; std::cin >> r; std::vector<bool> v(n); std::fill(v.begin(), v.begin() + r, true); do { for (int i = 0; i < n; ++i) { if (v[i]) { std::cout << (i + 1) << " "; } } std::cout << "\n"; } while (std::prev_permutation(v.begin(), v.end())); return 0; } 

一点解释:

它通过创build一个“select数组”( v )来工作,在这里我们放置rselect器,然后创build这些select器的所有排列,如果在v的当前排列中select了它,则打印相应的组成员。 希望这可以帮助。

如果你注意到,你可以实现它,为每个级别rselect一个从1到n的数字

在C ++中,我们需要“手动”保持产生结果的调用之间的状态(一个组合):所以,我们build立一个在构造初始化状态的类,并且每个调用都有一个成员返回组合, : 例如

 #include <iostream> #include <iterator> #include <vector> #include <cstdlib> using namespace std; struct combinations { typedef vector<int> combination_t; // initialize status combinations(int N, int R) : completed(N < 1 || R > N), generated(0), N(N), R(R) { for (int c = 1; c <= R; ++c) curr.push_back(c); } // true while there are more solutions bool completed; // count how many generated int generated; // get current and compute next combination combination_t next() { combination_t ret = curr; // find what to increment completed = true; for (int i = R - 1; i >= 0; --i) if (curr[i] < N - R + i + 1) { int j = curr[i] + 1; while (i <= R-1) curr[i++] = j++; completed = false; ++generated; break; } return ret; } private: int N, R; combination_t curr; }; int main(int argc, char **argv) { int N = argc >= 2 ? atoi(argv[1]) : 5; int R = argc >= 3 ? atoi(argv[2]) : 2; combinations cs(N, R); while (!cs.completed) { combinations::combination_t c = cs.next(); copy(c.begin(), c.end(), ostream_iterator<int>(cout, ",")); cout << endl; } return cs.generated; } 

testing输出:

 1,2, 1,3, 1,4, 1,5, 2,3, 2,4, 2,5, 3,4, 3,5, 4,5, 
  #include<iostream> using namespace std; for(int i=1;i<=5;i++) for (int j=2;j<=5;j++) if (i!=j) cout<<i<<","<<j<<","<<endl; //or instead of cout... you can put them in a matrix nx 2 and use the solution 

我build议搞清楚如何在纸上自己做,并从中推断出伪代码。 之后,你只需要决定编码和存储操作数据的方式。

例如:

 For each result item in result array // 0, 1, ... r For each item possible // 0, 1, 2, ... n if current item does not exist in the result array place item in result array exit the inner for end if end for end for 

您可以使用recursion来selectN + 1个组合,然后selectN个组合,然后加1。 您添加的1必须始终在N的最后一个之后,因此如果您的N包含最后一个元素,则不会有N + 1个相关的组合。

也许不是最有效的解决scheme,但它应该工作。

基本情况将select0或1.你可以select0并获得一个空集。 从一个空集合,你可以假设迭代器在元素之间而不是在元素之间工作。

代码类似于生成二进制数字。 保持一个额外的数据结构,一个数组perm [],其值在索引我会告诉如果第i个数组元素是否包含。 并保持一个计数variables。 每当计数==组合的长度时,打印基于perm []的元素。

 #include<stdio.h> // a[] : given array of chars // perm[] : perm[i] is 1 if a[i] is considered, else 0 // index : subscript of perm which is to be 0ed and 1ed // n : length of the given input array // k : length of the permuted string void combinate(char a[], int perm[],int index, int n, int k) { static int count = 0; if( count == k ) { for(int i=0; i<n; i++) if( perm[i]==1) printf("%c",a[i]); printf("\n"); } else if( (n-index)>= (k-count) ){ perm[index]=1; count++; combinate(a,perm,index+1,n,k); perm[index]=0; count--; combinate(a,perm,index+1,n,k); } } int main() { char a[] ={'a','b','c','d'}; int perm[4] = {0}; combinate(a,perm,0,4,3); return 0; } 

这是一个recursion的方法,你可以使用任何types。 你可以遍历一个Combinations类的实例(例如get或者vector),每个组合都是一个对象的向量,它是用C ++ 11编写的。

 //combinations.hpp #include <vector> template<typename T> class Combinations { // Combinations(std::vector<T> s, int m) iterate all Combinations without repetition // from set s of size ms = {0,1,2,3,4,5} all permuations are: {0, 1, 2}, {0, 1,3}, // {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5}, // {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, // {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5} public: Combinations(std::vector<T> s, int m) : M(m), set(s), partial(std::vector<T>(M)) { N = s.size(); // unsigned long can't be casted to int in initialization out = std::vector<std::vector<T>>(comb(N,M), std::vector<T>(M)); // allocate space generate(0, N-1, M-1); }; typedef typename std::vector<std::vector<T>>::const_iterator const_iterator; typedef typename std::vector<std::vector<T>>::iterator iterator; iterator begin() { return out.begin(); } iterator end() { return out.end(); } std::vector<std::vector<T>> get() { return out; } private: void generate(int i, int j, int m); unsigned long long comb(unsigned long long n, unsigned long long k); // C(n, k) = n! / (nk)! int N; int M; std::vector<T> set; std::vector<T> partial; std::vector<std::vector<T>> out; int count (0); }; template<typename T> void Combinations<T>::generate(int i, int j, int m) { // combination of size m (number of slots) out of set[i..j] if (m > 0) { for (int z=i; z<j-m+1; z++) { partial[Mm-1]=set[z]; // add element to permutation generate(z+1, j, m-1); } } else { // last position for (int z=i; z<j-m+1; z++) { partial[Mm-1] = set[z]; out[count++] = std::vector<T>(partial); // add to output vector } } } template<typename T> unsigned long long Combinations<T>::comb(unsigned long long n, unsigned long long k) { // this is from Knuth vol 3 if (k > n) { return 0; } unsigned long long r = 1; for (unsigned long long d = 1; d <= k; ++d) { r *= n--; r /= d; } return r; } 

testing文件:

 // test.cpp // compile with: gcc -O3 -Wall -std=c++11 -lstdc++ -o test test.cpp #include <iostream> #include "combinations.hpp" struct Bla{ float x, y, z; }; int main() { std::vector<int> s{0,1,2,3,4,5}; std::vector<Bla> ss{{1, .4, 5.0},{2, .7, 5.0},{3, .1, 2.0},{4, .66, 99.0}}; Combinations<int> c(s,3); // iterate over all combinations for (auto x : c) { for (auto ii : x) std::cout << ii << ", "; std::cout << "\n"; } // or get a vector back std::vector<std::vector<int>> z = c.get(); std::cout << "\n\n"; Combinations<Bla> cc(ss, 2); // combinations of arbitrary objects for (auto x : cc) { for (auto b : x) std::cout << "(" << bx << ", " << by << ", " << bz << "), "; std::cout << "\n"; } } 

输出是:

0,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2] 3个,5个,4个,5个,4个,5个,1个,4个,5个,2个,3个, 4个,2个,3个,5个,2个,4个,5个,3个,4个,5个,

(1,0.4,5),(1,0,0.5),(1,0.4,5),(3,0.1,2),(1,0.4,5),(4,0.66,99),(2 (3,0.1,2),(2,0.7,5),(4,0.66,99),(3,0.1,2),(4,0.66,99),

 void print(int *a, int* s, int ls) { for(int i = 0; i < ls; i++) { cout << a[s[i]] << " "; } cout << endl; } void PrintCombinations(int *a, int l, int k, int *s, int ls, int sp) { if(k == 0) { print(a,s,ls); return; } for(int i = sp; i < l; i++) { s[k-1] = i; PrintCombinations(a,l,k-1,s,ls,i+1); s[k-1] = -1; } } int main() { int e[] = {1,2,3,4,5,6,7,8,9}; int s[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; PrintCombinations(e,9,6,s,6,0); } 

对于(nselectr)的特例,其中r是一个固定的常数,我们可以写出r个嵌套的循环来达到这种情况。 有时当r不固定的时候,我们可能会有另一个特例(n选nr) ,其中r又是一个固定的常量。 这个想法是,每个这样的组合是(nselectr)的组合的逆。 所以我们可以再次使用r嵌套循环,但反转解决scheme:

 // example 1: choose each 2 from given vector and apply 'doSomething' void doOnCombinationsOfTwo(const std::vector<T> vector) { for (int i1 = 0; i1 < vector.size() - 1; i1++) { for (int i2 = i1 + 1; i2 < vector.size(); i2++) { doSomething( { vector[i1], vector[i2] }); } } } // example 2: choose each n-2 from given vector and apply 'doSomethingElse' void doOnCombinationsOfNMinusTwo(const std::vector<T> vector) { std::vector<T> combination(vector.size() - 2); // let's reuse our combination vector for (int i1 = 0; i1 < vector.size() - 1; i1++) { for (int i2 = i1 + 1; i2 < vector.size(); i2++) { auto combinationEntry = combination.begin(); // use iterator to fill combination for (int i = 0; i < vector.size(); i++) { if (i != i1 && i != i2) { *combinationEntry++ = i; } } doSomethingElse(combinationVector); } } } 

基于Nathan Wodarz教授algorithm的简单高效的解决scheme:

 // n choose r combination #include <vector> #include <iostream> #include <algorithm> struct c_unique { int current; c_unique() {current=0;} int operator()() {return ++current;} } UniqueNumber; void myfunction (int i) { std::cout << i << ' '; } int main() { int n=5; int r=3; std::vector<int> myints(r); std::vector<int>::iterator first = myints.begin(), last = myints.end(); std::generate(first, last, UniqueNumber); std::for_each(first, last, myfunction); std::cout << std::endl; while((*first) != n-r+1){ std::vector<int>::iterator mt = last; while (*(--mt) == n-(last-mt)+1); (*mt)++; while (++mt != last) *mt = *(mt-1)+1; std::for_each(first, last, myfunction); std::cout << std::endl; } } 

那么输出是:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

 public static class CombinationGenerator { int n; int k; Integer[] input; List<List<Integer>> output; public CombinationGenerator(int n, int k) { this.n = n; this.k = k; input = new Integer[n]; for (int i = 1; i <= n; i++) { input[i-1] = i; } } public List<List<Integer>> generate(){ if(k>n){ throw new RuntimeErrorException(null, "K should be less than N"); } output = generate(0, k); printOutput(); return output; } private List<List<Integer>> generate(int cur, int k) { List<List<Integer>> output = new ArrayList<List<Integer>>(); int length = input.length - cur; if(length == k){ List<Integer> result = new ArrayList<Integer>(); for (int i = cur; i < input.length; i++) { result.add(input[i]); } output.add(result); } else if( k == 1){ for (int i = cur; i < input.length; i++) { List<Integer> result = new ArrayList<Integer>(); result.add(input[i]); output.add(result); } } else{ for (int i = cur; i < input.length; i++) { List<List<Integer>> partialResult = generate(i+1, k-1); for (Iterator<List<Integer>> iterator = partialResult.iterator(); iterator .hasNext();) { List<Integer> list = (List<Integer>) iterator.next(); list.add(input[i]); } output.addAll(partialResult); } } return output; } private void printOutput(){ for (Iterator<List<Integer>> iterator = output.iterator(); iterator .hasNext();) { printList((List<Integer>) iterator.next()); } } private void printList(List<Integer> next) { for (Iterator<Integer> iterator = next.iterator(); iterator.hasNext();) { Integer integer = (Integer) iterator.next(); System.out.print(integer.intValue()); } System.out.print("\n"); } }