Skip to content

Instantly share code, notes, and snippets.

@ssanin82
Last active August 29, 2015 14:11
Show Gist options
  • Save ssanin82/070e7b50dd17aa0bc309 to your computer and use it in GitHub Desktop.
Save ssanin82/070e7b50dd17aa0bc309 to your computer and use it in GitHub Desktop.
C++: Getting all k-length combinations of n numbers
#include <iostream>
#include <vector>
using namespace std;
class Combinations {
int n;
int k;
vector<int> current;
bool init;
public:
Combinations(int n, int k): n(n), k(k), init(false) {
current.resize(k);
}
bool next() {
if (!init) {
int val = 0;
for (vector<int>::iterator it = current.begin();
it != current.end(); ++it) {
*it = val++;
}
init = true;
} else {
vector<int>::iterator it = current.end() - 1;
while (true) {
if (*it < (n - 1)) {
bool yield = true;
int m = ++*it;
while (++it != current.end()) {
if (m < (n - 1)) {
*it = ++m;
} else {
--it;
yield = false;
break;
}
}
if (yield) {
break;
}
} else {
if (current.begin() == it) {
return false;
} else {
--it;
}
}
}
}
return true;
}
const vector<int> &access() const {
return current;
}
void dump() const {
for (vector<int>::const_iterator it = current.begin();
it != current.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
};
int main() {
Combinations cmb(5, 2);
while(cmb.next()) {
cmb.dump();
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment