10
\$\begingroup\$

I wrote this as an attempt to create a non-recursive solution to project euler 60 which is basically finding a specific n choose k combination. The difference is that partial combinations can be invalid so this algorithm can reject whole swaths of combinations if the first part of the combination is wrong. Once the algorithm finds a complete combination it falls through and the calling function can use the "stack" which contains the combination. If the function is called again with that stack it gets the next complete combination. Any recommendations for improvements (performance, readability etc.) would be welcome.

#include <vector>   
#include <algorithm>   
#include <sstream>   


using namespace std;   

/// @brief An iterative algorithm to generate n choose k combinations   
/// @param n - Vector of possible values that n be chosen from   
/** @param valid - A check to see if a partial combination is valid   
 * For a typical n choose k any partial combination is valid*/   
///@param complete - A check to see if a given combination is fully vaild   
/**@param stack - A variable that holds the current combination. The function   
 * can be called again with the updated stack to get the next combination*/   
template<typename T, typename A>   
void n_choose_k(vector<T, A> *n, bool (*valid)(vector<typename vector<T, A>::iterator> stack),   
                bool (*complete)(vector<typename vector<T, A>::iterator> stack),   
                vector<typename vector<T, A>::iterator> *stack) {   

    bool firstCall= true;   

    //The first time this gets called we need to populate the stack   
    //On subsequent calls the flag remains set so that the stack advances and doesn't return a duplicate combination   
    if (stack->size() < 1) {   
        stack->push_back(n->begin());   
        firstCall= false;   
    }   

    //As soon as we find a complete combination fall through   
    //complete in general means the combination is long enough(k) and that it is valid   
    //for typical n choose k everything is valid   
    while (!complete(*stack) || firstCall) {   
        //If the last element is at the end of the n iterator or we've set the 2nd pass flag   
        if (n->end() - stack->back() <= 1 || firstCall) {   
            //iterate through the stack and either   
            for (int i = 0; n->end() - stack->back() <= i + 1; i++) {   
                //clear the stack and return if all possibilities have been exhausted   
                if (stack->size() == 1) {   
                    stack->clear();   
                    return;   
                }   
                //or pop the last element of any stack that is a "conflict set"   
                //that is any stack that couldn't possibly be complete   
                //ie (1, 6, __) in (1,2,3,4,5,6) choose 3 as there is nothing   
                //greater than 6 and the elements go in ascending order   
                stack->pop_back();   
            }   
            //Advance to the next combination   
            stack->back()++;   

            //unset the flag and continue so we don't skip combinations   
            if (firstCall) {   
                firstCall= false;   
                continue;   
            }   
        }   


        //If the current partial combination(stack) is valid   
        if (valid(*stack)) {   
            stack->push_back(stack->back());   
        }   
        //And advance to the next combination   
        stack->back()++;   
    }   
}   

And here's an example of how it could be called:

#include <cstdlib>
#include <iostream>
#include <vector>


bool valid(vector<vector<int>::iterator>  stack){
    return true;
}

bool complete(vector<vector<int>::iterator>  stack){
    return stack.size() == 3;
}

int main(void) {
    vector<int> n = {1, 2, 3, 4, 5};
    vector<vector<int>::iterator> stack;
    do {
        n_choose_k(&n, &valid, &complete, &stack);
        for (size_t i = 0; i < stack.size(); i++) {
            cout << *stack[i] << ", ";
        }
        cout << endl;
    } while (!stack.empty());

    return 0;
}

And that will output:

1, 2, 3,

1, 2, 4,

1, 2, 5,

1, 3, 4,

1, 3, 5,

1, 4, 5,

2, 3, 4,

2, 3, 5,

2, 4, 5,

3, 4, 5,

\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

Avoid using namespace std

It's a bad habit that will cause problems in bigger programs. Just don't.

Don't overly restrict argument types

The function is templated on both element type and allocator. If instead it's templated on the collection type, we can obtain both of those types from the collection itself:

template<typename Collection>
void n_choose_k(Collection *n, bool(*valid)(std::vector<typename Collection::iterator>),
                bool(*complete)(std::vector<typename Collection::iterator>),
                std::vector<typename Collection::iterator> *stack)

You might allow the caller to specify the output type:

template<typename Collection, typename Subset = std::vector<typename Collection::iterator>>
void n_choose_k(Collection *n,
                bool (*valid)(const Subset&),
                bool (*complete)(const Subset&),
                Subset *stack)

Prefer references over pointers where possible, and prefer const over mutable

Several of the arguments are accepted as pointers, but never checked against null. These can be passed as references:

template<typename Collection, typename Subset = std::vector<typename Collection::const_iterator>>
void n_choose_k(const Collection& n,
                bool (*valid)(const Subset&),
                bool (*complete)(const Subset&),
                Subset& stack)

I made n a reference to a constant Collection - this is important, as we are storing its iterators. It also has a knock-on effect on the type of the iterators used.

Consider allowing arbitrary function-like types

Currently, valid and complete are function pointers. More generic templates accept any callable object. Here's an example:

template<typename Collection,
         typename Subset = std::vector<typename Collection::const_iterator>,
         typename Predicate1 = std::function<bool(const Subset&)>,
         typename Predicate2 = std::function<bool(const Subset&)>>
void n_choose_k(const Collection& n,
                Predicate1 valid,
                Predicate2 complete,
                Subset& stack)

I can now call it with lambdas for either or both predicates:

    n_choose_k(v, [](auto&){return true;}, check_complete, stack);

You might consider passing a single function, returning an enumerated type {INVALID, INCOMPLETE, VALID} rather than two separate predicates.

Indicate end-of-sequence in the return value

At the moment, end of sequence is indicated by an empty stack returned, and so this must be tested for in the caller:

while (n_choose_k(v, [](auto&){return true;}, check_complete, stack), !stack.empty()) {

(This is incorrect in the example main(), which prints an empty line at the end).

If we make n_choose_k return a true value when complete is satisfied, and a false value when we run out of permutations, we can simplify the caller to

while (n_choose_k(v, [](auto&){return true;}, check_complete, stack))

This is also more similar to the std::next_permutation() algorithm, so less surprising to users.

Prefer preincrement

If there's no use for the old value, it can be more efficient to use prefix ++ rather than the postfix version:

        ++stack.back();

Use empty() instead of testing a collection's size

Instead of stack.size() < 1, we can write stack.empty(). It doesn't make much difference to performance for a vector, but it's a good habit when you might be using other collection classes, and it makes the intent clearer.

Document the requirements on valid and complete

In the toy example, it seems that we can eliminate many subsets in the validity check by returning false early if stack.size() > k. Alternatively, pass k into n_choose_k().

bool check_valid(const std::vector<std::vector<int>::const_iterator>&)
{
    return stack.size() <= 3;
}
bool check_complete(const std::vector<std::vector<int>::const_iterator>&  stack)
{
    return stack.size() == 3;
}

Consider making this a class

As the function is intended to be called multiple times with the same arguments, that smells very much like state. Consider encapsulating all those arguments into a constructor, and then have the client code just call a method to advance to the next valid subset.

Here's a complete worked example using a mutable class instead of a function:

#include <functional>
#include <vector>

// C++ Concepts: template<ForwardIterator It>

template<typename It>
class SubsetChooser
{
    using Subset = std::vector<It>;
    using Predicate = std::function<bool(const Subset&)>;

    const It first;
    const It last;
    const size_t subset_size;
    const Predicate is_valid;

    Subset state;

public:
    SubsetChooser(It first, It last, size_t subset_size, SubsetChooser<It>::Predicate is_valid);
    const Subset& subset() const;
    bool advance();
};

//---
// factory methods

template<typename It, typename Predicate>
auto make_chooser(It first, It last, size_t subset_size, Predicate is_valid)
{
    return SubsetChooser<It>{first, last, subset_size, is_valid};
}
template<typename Container, typename Predicate>
auto make_chooser(const Container& c, size_t subset_size, Predicate is_valid)
{
    using std::begin;
    using std::end;
    return make_chooser(begin(c), end(c), subset_size, is_valid);
}

//---
// private helpers

// Calculate it+n==end, without requiring a BidirectionalIterator
template<typename Iter, typename Distance>
bool is_n_from(Iter it, Distance n, const Iter& end)
{
    std::advance(it, n);
    return it == end;
}

//---
// implementation

template<typename It>
SubsetChooser<It>::SubsetChooser(It first, It last, size_t subset_size, SubsetChooser<It>::Predicate is_valid)
    : first{first}, last{last},
      subset_size{subset_size},
      is_valid{is_valid},
      state{}
{
    state.reserve(subset_size);
}

template<typename It>
const typename SubsetChooser<It>::Subset& SubsetChooser<It>::subset() const
{
    return state;
}

template<typename It>
bool SubsetChooser<It>::advance()
{
    do {
        if (state.empty()) {
            state.push_back(first);
        } else {
            if (state.size() < subset_size && is_valid(state)) {
                state.push_back(state.back());
            }

            // Roll over when the remaining elements wouldn't fill the subset.
            while (is_n_from(++state.back(), subset_size - state.size(), last)) {
                state.pop_back();
                if (state.empty())
                    // we have run out of possibilities
                    return false;
            }
        }
    } while (state.size() < subset_size || !is_valid(state));
    return true;
}

//---
// test program

// selects combinations of only odd elements
#include <algorithm>
bool is_odd(std::vector<int>::const_iterator n) { return *n%2; }
bool check_valid(const std::vector<std::vector<int>::const_iterator>& stack) { return std::all_of(stack.begin(), stack.end(), is_odd); }

#include <iostream>
int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7};
    auto chooser = make_chooser(v, 3, check_valid);

    while (chooser.advance()) {
        for (auto it: chooser.subset()) {
            std::cout << *it << ", ";
        }
        std::cout << std::endl;
    }

    return 0;
}
\$\endgroup\$
2
\$\begingroup\$

Without commenting on the algorithm, the API you've chosen is confusing.

Interface

Your docs don't really explain what valid and complete are for. What are some sensible implementations? From reading your example code, I see that valid can return true for any input and complete can return true for any input of length k. Are there others? For what purpose are you generalizing the interface? Unless you have some concrete implementations that solve problems that need solving, simplify your interface by replacing valid and complete by k.

Names

With valid and complete as arguments, this function isn't really n_choose_k. next_combination might be a better name, or next_subset. Even if you did omit valid and complete and passed k instead, n_choose_k is inappropriate; I would expect such a function to have the signature

// Returns the number of combinations of size k from a set of n elements.
template <typename Int>
Int n_choose_k(Int n, Int k);

n isn't the best name -- in the context of naming the function n_choose_k, n means two different things -- the set and the size of the set.

valid and complete are OK but not great; their meaning isn't clear without reading the documentation of the function.

stack is a poor name. As an implementation detail, you are treating it as a stack, but from the caller's point of view, this would be better as combination or subset.

Types

Toby Speight's answer addressed this a bit already, but I wanted to tack on a few more points.

First, you're over-specifying types.

  • Instead of specifying vector<T, A>, allow an arbitrary collection, or better yet, pass iterators. I think you can implement this algorithm with the forward iterator concept.
  • You're requiring that valid and complete are pointers to functions with specific signatures. You forbid lambdas and other callable objects, or functions with compatible signatures. Consider const std::function<bool(const Subset&)>& or even templating on the callable type.

You're also using pointers where you ought to use references, omitting const where you oughtn't, and passing by value to valid and complete where you ought to pass by reference.

template <typename ForwardIt, typename ValidFn, 
          typename CompleteFn, typename Subset>
void next_subset(ForwardIt b, ForwardIt e, const ValidFn& valid,
                 const CompleteFn& complete, Subset& subset);
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Again, we cross each other in flight - I made a similar point about the callback functions. Good points on the naming - and next_subset() would sound much more like std::next_permutation() for improved recognition. \$\endgroup\$ Commented Jun 2, 2017 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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