4
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Xam Apr 1 '18 at 18:02
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – yuri Apr 1 '18 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.