#include <iostream>
using std::cout;
// C(n, r) and provide the current combination set a of size r.
bool nextCombination(int n, int r, int *a);
void printArray(int *a, int n);
int main() {
int a[] = {1,2,3};
int length = sizeof(a)/sizeof(*a);
int count = 0;
// The following example is C(7,3), start at {1,2,3}
do {
printArray(a, length);
count++;
} while (nextCombination(7, length, a));
cout << "Total: " << count << '\n';
return 0;
}
bool nextCombination(int n, int r, int *a) {
int lastNotEqualOffset = r-1;
while (a[lastNotEqualOffset] == n-r+(lastNotEqualOffset+1)) {
lastNotEqualOffset--;
}
if (lastNotEqualOffset < 0) {
cout << "the end\n";
return false;
}
a[lastNotEqualOffset]++;
for (int i = lastNotEqualOffset+1; i<r; i++) {
a[i] = a[lastNotEqualOffset]+(i-lastNotEqualOffset);
}
return true;
}
void printArray(int *a, int n) {
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << '\n';
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBzdGQ6OmNvdXQ7CgovLyBDKG4sIHIpIGFuZCBwcm92aWRlIHRoZSBjdXJyZW50IGNvbWJpbmF0aW9uIHNldCBhIG9mIHNpemUgci4KYm9vbCBuZXh0Q29tYmluYXRpb24oaW50IG4sIGludCByLCBpbnQgKmEpOwp2b2lkIHByaW50QXJyYXkoaW50ICphLCBpbnQgbik7CgppbnQgbWFpbigpIHsKCWludCBhW10gPSB7MSwyLDN9OwoJaW50IGxlbmd0aCA9IHNpemVvZihhKS9zaXplb2YoKmEpOwoJaW50IGNvdW50ID0gMDsKCS8vIFRoZSBmb2xsb3dpbmcgZXhhbXBsZSBpcyBDKDcsMyksIHN0YXJ0IGF0IHsxLDIsM30KCWRvIHsKCQlwcmludEFycmF5KGEsIGxlbmd0aCk7CgkJY291bnQrKzsKCX0gd2hpbGUgKG5leHRDb21iaW5hdGlvbig3LCBsZW5ndGgsIGEpKTsKCWNvdXQgPDwgIlRvdGFsOiAiIDw8IGNvdW50IDw8ICdcbic7CglyZXR1cm4gMDsKfQoKYm9vbCBuZXh0Q29tYmluYXRpb24oaW50IG4sIGludCByLCBpbnQgKmEpIHsKCWludCBsYXN0Tm90RXF1YWxPZmZzZXQgPSByLTE7Cgl3aGlsZSAoYVtsYXN0Tm90RXF1YWxPZmZzZXRdID09IG4tcisobGFzdE5vdEVxdWFsT2Zmc2V0KzEpKSB7CgkJbGFzdE5vdEVxdWFsT2Zmc2V0LS07Cgl9CglpZiAobGFzdE5vdEVxdWFsT2Zmc2V0IDwgMCkgewoJCWNvdXQgPDwgInRoZSBlbmRcbiI7CgkJcmV0dXJuIGZhbHNlOwoJfQoJYVtsYXN0Tm90RXF1YWxPZmZzZXRdKys7Cglmb3IgKGludCBpID0gbGFzdE5vdEVxdWFsT2Zmc2V0KzE7IGk8cjsgaSsrKSB7CgkJYVtpXSA9IGFbbGFzdE5vdEVxdWFsT2Zmc2V0XSsoaS1sYXN0Tm90RXF1YWxPZmZzZXQpOwoJfQoJcmV0dXJuIHRydWU7Cn0KCnZvaWQgcHJpbnRBcnJheShpbnQgKmEsIGludCBuKSB7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCWNvdXQgPDwgYVtpXSA8PCAiICI7Cgl9Cgljb3V0IDw8ICdcbic7Cn0KCgo=