Counting partitions in C++ using STL

user_4858640 0
Viewed 82

Imagine I have a container C containing elements of some type T and a predicate with which to determine if any two variables of type T are "equivalent". E.g. if T is int I might have a predicate eqv = [](int a, int b){ return a % 5 == b % 5; } such that two integers are equivalent under eqv if they have the same remainder when divided by five.

Given such a container and a predicate, is there some STL function (e.g. from algorithm) which which I can elegantly (i.e. without writing a lot of code myself) determine the number of partitions of C under eqv?

For example, if eqv is as above and C is std::vector<int>{1,2,3,6,7,8} I would like to obtain the result 3 (because the equivalence classes are {1,6}, {2,7} and {3,8}).

stl c++
1 Answers

Two approaches, depending on what you can also do with T:

  • if you can somehow order these equivalence classes, then create a std::set. The sorting of objects of type T needs to be a non-total order, where all elements which are equivalent under your predicate are neither less nor not less than the other elements of their class. Insert all elements, then count the set's size.

  • if you can somehow compute a hash of these equivalence classes, then create a std::unordered_set with the template parameter KeyEqual set to your predicate. Insert all elements, then count the set's size.

If you only have the predicate, then I guess you're stuck with counting:

#include <algorithm>
#include <iostream>
#include <vector>



int main() {
    std::vector<int> elements = {1, 2, 3, 6, 7, 8};
    
    unsigned int size = 0;
    while (elements.size() > 0)
    {
        int const current = elements.front();
        auto pred = [&current] (auto const & other) {
            return (current % 5) == (other % 5);
        };
        elements.erase(std::remove_if(begin(elements), end(elements), pred), end(elements));
        ++size;
    }
    
    std::cout << size << " equivalence classes" << std::endl;
}

Isn't that much code, after all.

user_11163640
Related