在c ++中生成组合
我一直在寻找一个使用c ++来生成组合的源代码。 我发现了一些高级的代码，但是这只适用于特定数量的预定义数据。 任何人都可以给我一些提示，或者也许有一些想法来产生组合。 作为一个例子，假设集合S = {1,2,3，…，n}，我们从中选取r = 2。 input将是n和r 。在这种情况下，程序将生成长度为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"); } }
