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:


The size n of a integer set {1, 2, ..., n}, which is where you choose objects from.
The size r of the subset of the integer set you currently have.
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 &lt;iostream&gt;
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 &lt;&lt; "Total: " &lt;&lt; count &lt;&lt; '\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 &lt; 0) {
        cout &lt;&lt; "the end\n";
        return false;
    }
    a[lastNotEqualOffset]++;
    for (int i = lastNotEqualOffset+1; i&lt;r; i++) {
        a[i] = a[lastNotEqualOffset]+(i-lastNotEqualOffset);
    }
    return true;
}

void printArray(int *a, int n) {
    for (int i = 0; i &lt; n; i++) {
        cout &lt;&lt; a[i] &lt;&lt; " ";
    }
    cout &lt;&lt; '\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 better than including the entire namespace, is 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 program 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&lt;&lt; to print the current line.
Eliminate magic numbers.


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

#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;vector&gt;

class Combinatorics {
public:
    Combinatorics(std::vector&lt;int&gt; const&amp; v, int const&amp; n, int const&amp; r)
        : elements{v}
        , n{n}
        , r{r}
    {}

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

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

private:
    std::vector&lt;int&gt; elements;
    int n;
    int r;
};

std::ostream&amp; operator&lt;&lt;(std::ostream&amp; os, Combinatorics const&amp; obj) {
    std::copy(obj.elements.begin(), obj.elements.end(), std::ostream_iterator&lt;int&gt;(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 &lt;&lt; combinatorics &lt;&lt; "\n";
        ++total;
    } while (combinatorics.next());
    std::cout &lt;&lt; total &lt;&lt; "\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).