given a sorted sequence and an integer N, generate all sorted subsequences with size N
GoogleCodeExporter opened this issue · 0 comments
GoogleCodeExporter commented
#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