combination

#include <boost/range.hpp>
#include <vector>

template <typename t, typename op_t>
struct combination : private op_t, boost::noncopyable
{
    std::vector<t> res_;
    combination(int n, op_t op) : op_t(op), res_(n) {}
    template <typename iterator> void com(iterator begin, iterator end, int n);
};

template <typename t, typename op_t>
template <typename iterator>
void combination<t, op_t>::com(iterator begin, iterator end, int n)
{
    if (n == 1)
    {
        for ( ; begin != end; ++begin)
        {
            res_.back() = *begin;
            this->operator()(boost::begin(res_), boost::end(res_));
        }
        return;
    }

    while (begin + n < end)
    {
        res_[res_.size()-n] = *begin;
        this->com(++begin, end, n-1);
    }

    for ( ; begin != end; ++begin, --n)
        res_[res_.size()-n] = *begin;
    this->operator()(boost::begin(res_), boost::end(res_));
}

template <typename rng_t, typename op_t>
inline void combine(rng_t& r, int n, op_t op)
{
    typedef typename boost::range_value<rng_t>::type type;
    combination<type, op_t>(n, op).com(boost::begin(r), boost::end(r), n);
}


#include <algorithm>
#include <iostream>

struct Print
{
    template <typename iterator>
    void operator()(iterator begin, iterator end) const
    {
        typedef typename std::iterator_traits<iterator>::value_type type;
        std::vector<type> buf(begin, end);
        do
        {
            std::copy(buf.begin(), buf.end(), std::ostream_iterator<type>(std::cout));
            std::cout << " ";
        } while (std::next_permutation(buf.begin(), buf.end()));
        std::cout << std::endl;
    }
};

int
main(int argc, char* const argv[])
{
    char s[] = "12345";
    combine(s, 3, Print());
}


#if 0
123 132 213 231 312 321 
124 142 214 241 412 421 
125 152 215 251 512 521 
134 143 314 341 413 431 
135 153 315 351 513 531 
145 154 415 451 514 541 
234 243 324 342 423 432 
235 253 325 352 523 532 
245 254 425 452 524 542 
345 354 435 453 534 543 
#endif