7
\$\begingroup\$

C++'s standard library has a std::next_permutation algorithm but no next_combination. The reason behind this absence is, I guess, that one of the easiest and fastest way to generate combinations one at a time is to rely on the permutations of a vector of boolean values, which is then used as a sieve to retain the elements in the combination. The drawback is that you need to maintain some state to compute the next permutation.

Here's a try at a STL style next_combination state-less algorithm. The range [begin, end) contains the whole set of elements, and [begin, begin+k) the current combination of k elements. The next combination is generated in place.

I'd be grateful for advice and improvement suggestions.

NB1: the algorithm depends on two invariants: [begin, begin+k] is sorted, and [begin+k, end) is sorted also.

NB2: I've tried to rely on existing STL algorithms as much as possible.

#include <algorithm>
#include <functional>

template <typename Iterator>
Iterator find_next_increase_position(Iterator begin, Iterator combination_end, Iterator end);

template <typename Iterator>
bool next_combination(Iterator begin, Iterator end, unsigned k) {
    const auto combination_end = begin+k;
    const auto next_move = find_next_increase_position(begin, combination_end, end);
    if (next_move == end) return false;
    const auto previous_value = *next_move;
    std::inplace_merge(next_move, combination_end, end);
    const auto next_rotation =
        std::rotate(next_move, std::upper_bound(next_move, end, previous_value), end);
    std::rotate(combination_end, next_rotation, end);
    return true;
}

template <typename Iterator>
Iterator find_next_increase_position(Iterator begin, Iterator combination_end, Iterator end) {
    auto pos = std::upper_bound(std::reverse_iterator(combination_end),
                                    std::reverse_iterator(begin),
                                    *--end,
                                    std::greater<typename Iterator::value_type>());
    if (pos.base() == begin)
        return ++end;
    return --pos.base();
}

An example:

#include <vector>

int main() {
    std::vector<int> test{1,2,3,4,5};
    while (next_combination(test.begin(), test.end(), 3)) {
        for (auto i : test) std::cout << i;    
        std::cout << std::endl;
    }
}

With output:

12435
12534
13425
13524
14523
23415
23514
24513
34512

Edit: added #includes and example

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you missing some #include lines? It looks like you need (at least) #include <algorithm> and #include <iterator>. \$\endgroup\$ – Toby Speight Jan 8 '18 at 14:32
1
\$\begingroup\$

My advice here is this: throw away your requirement of not having any state. The number sequence \$\binom{i}{\lceil i \rceil}\$ grows fast, so you won't be able to deal with combinations whose state is "large". Also, I see no point doing templates here. Instead you could write a simple class that manages indices in such a way that indirection is lexicographic:

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

class lexicographical_combination_generator {
public:
    lexicographical_combination_generator(size_t set_size,
                                          size_t combination_size);
    bool increment();
    size_t get_set_size()                      { return m_set_size; }
    size_t get_combination_size()              { return m_combination_size; }
    size_t get_combination_index(size_t index) { return m_indices[index]; }
private:
    size_t              m_set_size;
    size_t              m_combination_size;
    std::vector<size_t> m_indices;

    void check_arguments(size_t set_size, size_t combination_size);
};

lexicographical_combination_generator::
lexicographical_combination_generator(size_t set_size, size_t combination_size)
{
    check_arguments(set_size, combination_size);
    m_set_size = set_size;
    m_combination_size = combination_size;

    for (size_t index = 0; index < m_combination_size; ++index)
    {
        m_indices.push_back(index);
    }
}

void lexicographical_combination_generator::
check_arguments(size_t set_size, size_t combination_size)
{
    if (combination_size > set_size)
    {
        std::stringstream ss;
        ss << "combination_size("
           << combination_size
           << ") > set_size("
           << set_size
           << ")";
        throw std::runtime_error{ss.str()};
    }

    if (set_size == 0)
    {
        std::stringstream ss;
        ss << "set_size is zero";
        throw std::runtime_error{ss.str()};
    }
}

bool lexicographical_combination_generator::increment()
{
    if (m_indices[m_combination_size - 1] < m_set_size - 1)
    {
        m_indices[m_combination_size - 1]++;
        return true;
    }

    for (int i = (int)(m_combination_size - 2); i >= 0; --i)
    {
        if (m_indices[i] < m_indices[i + 1] - 1)
        {
            m_indices[i]++;

            for (int j = i + 1; j < m_combination_size; ++j)
            {
                m_indices[j] = m_indices[j - 1] + 1;
            }

            return true;
        }
    }

    return false;
}

template<typename Iter>
void print(lexicographical_combination_generator& gen, Iter begin)
{
    for (size_t i = 0; i < gen.get_combination_size(); ++i)
    {
        std::cout << gen.get_combination_index(i);
    }

    std::cout << ": ";

    for (size_t i = 0; i < gen.get_combination_size(); ++i)
    {
        auto iter = begin;
        std::advance(iter, gen.get_combination_index(i));
        std::cout << *iter;
    }

    std::cout << "\n";
}

int main(int argc, const char * argv[]) {
    std::vector<char> alphabet = { 'a', 'b', 'c', 'd', 'e' };
    lexicographical_combination_generator gen(5, 3);
    do {
        print(gen, alphabet.begin());
    } while (gen.increment());
}
\$\endgroup\$
  • \$\begingroup\$ My output is correct. You forgot to count the initial combination I didn't display in my example. // I'm still reading your post \$\endgroup\$ – papagaga Jan 8 '18 at 20:50
  • \$\begingroup\$ @papagaga Ok got it. My bad. \$\endgroup\$ – coderodde Jan 8 '18 at 20:51
  • \$\begingroup\$ @papagaga Ah, of course. You first increment 12345 and only after that you print it. \$\endgroup\$ – coderodde Jan 8 '18 at 20:53
  • \$\begingroup\$ A stateful algorithm wasn't my purpose. I believe stateless is an interesting goal because you can parallelize efficiently. Given a sorted range as input, two rotations are enough to create another starting point. For example: thread 1: "12345", thread2: "23415" (of course it would be useful only for longer sequences) \$\endgroup\$ – papagaga Jan 9 '18 at 9:37
  • \$\begingroup\$ @papagaga Fair enough. \$\endgroup\$ – coderodde Jan 9 '18 at 9:40

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.