# A little next combination program in C++

An implementation of next combination function at Discrete Mathematics and Its Applications, Rosen p.438.

## How it works:

Input:

1. The size n of a integer set {1, 2, ..., n}, which is where you choose objects from.
2. The size r of the subset of the integer set you currently have.
3. A pointer to the subset you currently have.

Output: The next subset in lexicographic order.

If you want to play around here is a link to ideone.com.

#include <iostream>
using std::cout;

// C(n, r) and provide the current subset 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}; // So the current subset is {1,2,3} of size 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'; // Since we start from {1,2,3}, all C(7,3) subsets are generated and counted. The answer should be 7!/(3!4!)=35
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';
}

The overview of its output:

1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 4
...
4 5 6
4 5 7
4 6 7
5 6 7
the end
Total: 35

using std::cout;, while this is better than including the entire namespace it's still worse than simply using the std:: prefix. If typing it annoys you too much, you can just make a macro in your editor to type it for you when you press a certain key combo.

Overall this looks much more like a C progamm than a C++ one. Assuming your algorithm works as intended you can take some steps to make this more C++ idiomatic.

• replace the array with a vector and get rid of raw pointers
• enforce const when possible
• drop return 0 from main because the compiler will generate it for you. This refers excplicitly to the return 0 at the end of main. Exiting from main by reaching the end automatically returns 0. So adding the return statement is just duplicate code.
• prefer prefix over postfix operator
• move the logic into a class so you don't have to pass everything on every call to nextCombination
• you can overload operator<< to print the current line
• eliminate magic numbers

Keeping all this in mind, the rewrite could look something like this:

#include <iostream>
#include <iterator>
#include <vector>

class Combinatorics {
public:
Combinatorics(std::vector<int> const& v, int const& n, int const& r)
: elements{v}
, n{n}
, r{r}
{}

friend std::ostream& operator<<(std::ostream& os, Combinatorics const& obj);

bool next() {
int lastNotEqualOffset = r - 1;
while (elements[lastNotEqualOffset] == n - r + (lastNotEqualOffset + 1)) {
--lastNotEqualOffset;
}
if (lastNotEqualOffset < 0) {
return false;
}
++elements[lastNotEqualOffset];
for (int i = lastNotEqualOffset + 1; i < r; ++i) {
elements[i] = elements[lastNotEqualOffset] + (i - lastNotEqualOffset);
}
return true;
}

private:
std::vector<int> elements;
int n;
int r;
};

std::ostream& operator<<(std::ostream& os, Combinatorics const& obj) {
std::copy(obj.elements.begin(), obj.elements.end(), std::ostream_iterator<int>(os, " "));
return os;
}

int main() {
constexpr int n = 7;
constexpr int r = 3;
int total = 0;
Combinatorics combinatorics{{1, 2, 3}, n, r};
do {
std::cout << combinatorics << "\n";
++total;
} while (combinatorics.next());
std::cout << total << "\n";
}

You simply pass all your data into the constructor upfront and then call next until every repetition has been done. (I kept n and r because they are used in the math context, normally you should try to avoid short variable names like that).

• Why using std::cout is still worse than std::? Btw, I can't still not fully understand why many people recommend to drop return 0 from main. Isn't that against the principle of least astonishment? I mean, if I a see a function that has an int in its declaration, I expect to see a return somewhere in the definition of such function. Why main should have a different treatment? – Xam Apr 1 '18 at 18:02
• @Xam I will edit the post to explain about return 0 in more detail. Regarding using std::cout, it still pollutes the namespace just on a smaller scale. – yuri Apr 1 '18 at 18:15