Advice on cleaning up this termination condition

Question

I've been playing with C++11 functional in order to do the same as python's itertools.combinations(input, 2), so far this is what I have:

EDIT removed outer lambda as suggested by @DavidRodríguez-dribeas

#include <iostream>
#include <functional>
#include <vector>

using namespace std;

template <class T>
function<pair<T*, T*>()> combinations(vector<T> & input) {
  auto it1 = input.begin();
  auto end = input.end();
  auto it2 = next(it1);
  return [=]() mutable {
      if (it2 == end) {
        it1++;
        it2 = next(it1);
      }   
      if (it2 != end)
        return pair<T*,T*>(&(*it1), &(*it2++));
      return pair<T*,T*>(&*end, &*end);
    };  
};

int main (void) {
  vector<int> numbers{1,2,3,4,5,6};
  auto func = combinations(numbers);
  while ( true ) { 
    auto i = func();
    if (i.first == &*(numbers.end())) break;
    cout << *(i.first) << ',' << *(i.second) << endl;
  }

  return 0;
};

I'm not happy with the method used to iterate over the combinations any advice on cleaning it up?

One thing that you can simplify code (not the condition) is removing the outer lambda, which is only used for a single execution... there is no point in doing so. Then to simplify the stop condition in `main` you can just drop the second lambda and use a proper functor (or store the lambda in a functor) that offers a test for completion (GoF iterator pattern). — David Rodríguez - dribeas, Nov 27 '12 at 17:58
There are several examples of iterating over combinations at: http://stackoverflow.com/questions/2211915/combination-and-permutation-in-c — James McNellis, Nov 27 '12 at 20:42
@GarethA.Lloyd I commented before you edited it and took out the erroneous code. — Seth Carnegie, Nov 27 '12 at 20:46
Seems like a question for Code Reviews rather than Stack Overflow. — Adrian McCarthy, Nov 27 '12 at 22:04

Howard Hinnant · Answer 1 · 2012-11-28T19:13:25.327

Here is documentation and code on my favorite way of doing this. And here is how that library would be used for your example:

#include <iostream>
#include <vector>
#include "combinations"

using namespace std;

int main (void) {
  vector<int> numbers{1,2,3,4,5,6};
  for_each_combination(numbers.begin(), numbers.begin()+2, numbers.end(),
           [](vector<int>::const_iterator b, vector<int>::const_iterator e)
           {
              if (b != e)
              {
                cout << *b;
                for (auto i = b+1; i != e; ++i)
                    cout << ',' << *i;
                cout << endl;
              }
              return false;
           });
}

1,2
1,3
1,4
1,5
1,6
2,3
2,4
2,5
2,6
3,4
3,5
3,6
4,5
4,6
5,6

Should the need arise, it is trivial to change the example use to consider 3 or 4 items at time instead of 2. One can also deal with various permutations k out of N at a time.

Update

Adding a level of indirection to illustrate how you would deal with a vector of items that were not efficient at moving/swapping around in the vector:

#include <iostream>
#include <vector>
#include "combinations"

using namespace std;

int main (void) {
  vector<int> numbers{1,2,3,4,5,6};
  vector<vector<int>::const_iterator> num_iters;
  num_iters.reserve(numbers.size());
  for (auto i = numbers.begin(); i != numbers.end(); ++i)
    num_iters.push_back(i);
  for_each_combination(num_iters.begin(), num_iters.begin()+2, num_iters.end(),
           [](vector<vector<int>::const_iterator>::const_iterator b,
              vector<vector<int>::const_iterator>::const_iterator e)
           {
              if (b != e)
              {
                cout << **b;
                for (auto i = b+1; i != e; ++i)
                    cout << ',' << **i;
                cout << endl;
              }
              return false;
           });
}

I was a bit surprised when testing your function for_each_combination that it actually mess up with the data in the vector and swap element around. I quite like the OP approach. I can imagine a more general solution where you pass r as a parameter (or maybe an integer template) so the function combinations would return some kind of generator that give at each call a r-tuple of iterator pointing to the next r-combination. It wouldn't touch the data at all, so can be used with heavy objects inside the vector. It's also maybe more efficient ? (I'm not sure). What do you think of this way to do ? — Arzar, Nov 28 '12 at 09:28
@ThomasPetit: That certainly seems like another viable interface. I believe one would have to code it up and test the two to make an informed decision on which interface/implementation served best. In my implementation move and swap are used exclusively (as opposed to copy) with the assumption that such things are usually efficient enough. That being said, one can certainly work up examples where that is not true. But one can also always fix such a problem by passing in a sequence of iterators or references to the original heavy objects, and thus achieve exactly what you are asking for. — Howard Hinnant, Nov 28 '12 at 19:03

Gareth A. Lloyd · Accepted Answer · 2012-12-03T19:52:51.507

I found out that Oliver Kowalke's coroutine library has been accepted by Boosts peer review and should be included hopefully in the next version. Jumping the gun a bit I gave it a go by using the coroutine branch of the boost-dev repo (https://gitorious.org/boost-dev/boost-dev).

g++ -I path/to/boost-dev -std=c++11 test_code.cpp -o run_test_code -static -L path/to/boost-dev/stage/lib/ -lboost_context

#include <boost/coroutine/all.hpp>
#include <boost/bind.hpp>
#include <boost/range.hpp>
#include <iostream>
#include <vector>

using namespace std;
using namespace boost;

template <typename T>
using coro_pairT_void = coroutines::coroutine<pair<T&,T&>(void)>;

template <typename T>
void combinations(typename coro_pairT_void<T>::caller_type & self, vector<T> & input ) { 
  for (auto it1 = input.begin(), itend = input.end(); it1 != itend; it1++) {
    for (auto it2 = std::next(it1); it2 != itend; it2++) {
      self(pair<T&, T&>(*it1,*it2));
    }   
  }
};

int main( void ) { 
  vector<int> numbers{1,2,3,4,5,6};
  coro_pairT_void<int> func(bind(combinations<int>, _1, numbers));
  for (auto it(begin(func)), itend(end(func)); it != itend; ++it) {
    cout << it->first << ',' << it->second << endl;
  }
  return 0;
};

Advice on cleaning up this termination condition

2 Answers2