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,