I have been searching a source code for generating combination using c++. I found some advanced codes for this but that is good for only specific number predefined data. Can anyone give me some hints, or perhaps, some idea to generate combination. As an example, suppose the set S = { 1, 2, 3, ...., n} and we pick r= 2 out of it. The input would be n
and r
.In this case, the program will generate arrays of length two, like 5 2 outputs 1 2, 1 3, etc.. I had difficulty in constructing the algorithm. It took me a month thinking about this.
This question is related to
c++
algorithm
combinations
A simple way using 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;
}
or a slight variation that outputs the results in an easier to follow order:
#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;
}
A bit of explanation:
It works by creating a "selection array" (v
), where we place r
selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v
.
You can implement it if you note that for each level r you select a number from 1 to n.
In C++, we need to 'manually' keep the state between calls that produces results (a combination): so, we build a class that on construction initialize the state, and has a member that on each call returns the combination while there are solutions: for instance
#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;
}
test output:
1,2,
1,3,
1,4,
1,5,
2,3,
2,4,
2,5,
3,4,
3,5,
4,5,
Source: Stackoverflow.com