given a sorted sequence and an integer N, generate all sorted subsequences with size N

[GoogleCodeExporter]

#include <iostream>
#include <type_traits>
#include <iterator>
#include <vector>

using namespace std;

template<typename T>
void genseq(T start, T end, int tam);

int main()
{
    char master[] = {'a','b','c','d','e'};
    for( int s = 0; s <= 6; ++s ) {
        genseq(master,master+5,s);
    }
}

// need one n sized subsequence starting at each element of the master sequence
// n sized subsequences starting in X are X + all n-1 sized subsequences after X
// a 0 sized subsequence defines its ending
// n sized subsequences starting in X when there are less than n-1 elements 
after X are discarded

template<typename T>
void genseq2(T start, T end, int tam, vector<typename 
iterator_traits<T>::value_type> & seq)
{
    if( tam == 0 ) {
        // emit seq and return
        copy(seq.begin(),seq.end(),ostream_iterator<typename iterator_traits<T>::value_type>(cout,","));
        cout << endl;
        return;
    }

    for( T x = start; x != end-tam+1; ++x ) {
        seq.push_back(*x);
        genseq2(x+1,end,tam-1,seq);
        seq.pop_back();
    }
}

template<typename T>
void genseq(T start, T end, int tam)
{
    cout << "generating sequences for size " << tam << endl;
    if( tam <= 0 || end-start < tam ) return;

    vector<typename iterator_traits<T>::value_type> seq;
    genseq2(start, end, tam, seq);
}

Original issue reported on code.google.com by jose.di...@gmail.com on 20 Jul 2012 at 4:46