Passing vectors as parameters to a recursive function

[lugal]

This might be more appropriate here. I'm new to C++, coming from a
background in another languages that allowed a similar solution to work
(Python). I wrote the following code in C++ based on the Python code
found here:

http://aspn.activestate.com/ASPN/Coo.../Recipe/302478

//beginning

#include <vector>
#include <iostream.h>
using namespace std;

void looper(vector <vector<int> > nseq, vector<int> comb);
vector <vector<int> > master;

int main() {
int n, C;
vector <vector<int> > seq;
vector<int> holder;
cout << "Enter constant: ";
cin >> C;
cout << "Enter n: ";
cin >> n;
for(i=0; i<=n; i++) {
vector <int> tmp;
for(int j=0; j<=C; j++) {
tmp.push_back(j);
}
seq.push_back(tmp);
}
looper(seq, holder);
return 0;
}

void looper(vector <vector<int> > nseq, vector<int> comb) {
if(nseq.size()>0) {
vector<int> tseq = nseq.at(0);
for(int i=0; i<tseq.size(); i++) {
vector <vector<int> > gseq = nseq;
vector<int> tcomb = comb;
gseq.erase(0);
tcomb.push_back(tseq[i]);
looper(gseq, tcomb);
}
} else {
master.push_back(comb);
}
}

// end

The program dies on the line:

tcomb.push_back(tseq[i]);

It seems vectors can't be passed effectively as parameters to recursive
functions (at least how I'm doing it). Is this true?

[Bogdan Sintoma]

lugal wrote:
[snip]

void looper(vector <vector<int> > nseq, vector<int> comb) {
if(nseq.size()>0) {
vector<int> tseq = nseq.at(0);
for(int i=0; i<tseq.size(); i++) {
vector <vector<int> > gseq = nseq;
vector<int> tcomb = comb;
gseq.erase(0); Try to replace the above line by "qseq.erase(1);" and see what your
compiler says about it ;) tcomb.push_back(tseq[i]);
looper(gseq, tcomb);
}
} else {
master.push_back(comb);
}
}

// end
[snip] It seems vectors can't be passed effectively as parameters to recursive functions (at least how I'm doing it). Is this true?

NO! :)

Best regards,
Bogdan Sintoma

[Jeff Schwab]

lugal wrote:

This might be more appropriate here. I'm new to C++, coming from a
background in another languages that allowed a similar solution to work
(Python). I wrote the following code in C++ based on the Python code
found here:

http://aspn.activestate.com/ASPN/Coo.../Recipe/302478
I don't as much python as I would like... What are you trying to do?
Sorry, sometimes code just ain't enough.

<snip> code reproduced below </>
It seems vectors can't be passed effectively as parameters to recursive
functions (at least how I'm doing it). Is this true?

Not at all, except that you might use up all of your machine's stack
space. :) Try passing big data structures by constant reference (const&
pronounced "const ref"). Here are a few fixes to try for now.

//beginning

#include <vector>
//#include <iostream.h>

// <iostream.h> is ancient. Use <iostream> instead.
#include <iostream>

using namespace std;

//void looper(vector <vector<int> > nseq, vector<int> comb);

// Passing big objects by value can be really inefficient. Try
// passing by reference instead:

void looper(
vector< vector< int > > const& nseq,
vector< int > const& comb );
vector <vector<int> > master;

// Why the global variable?

int main() {
int n, C;
vector <vector<int> > seq;
vector<int> holder;
cout << "Enter constant: ";
cin >> C;
cout << "Enter n: ";
cin >> n;
//for(i=0; i<=n; i++) {

// You have to declare the type of i.
for(int i=0; i<=n; i++) {

vector <int> tmp;
for(int j=0; j<=C; j++) {
tmp.push_back(j);
}
seq.push_back(tmp);
}
looper(seq, holder);
return 0;
}

//void looper(vector <vector<int> > nseq, vector<int> comb) {

void looper( vector <vector<int> > const& nseq,
vector<int> const& comb) {

if(nseq.size()>0) {
vector<int> tseq = nseq.at(0);

// You just copied a whole vector. Could be
// expensive.
for(int i=0; i<tseq.size(); i++) {
vector <vector<int> > gseq = nseq;
vector<int> tcomb = comb;

// Once again, these make copies of the
// vectors.

//gseq.erase(0);

// vector<>::erase wants an iterator, not an
// integer.

gseq.erase( gseq.begin( ) );

tcomb.push_back(tseq[i]);
looper(gseq, tcomb);
}
}
else {
master.push_back(comb);
}
}

// end

[Ivan Vecerina]

"lugal" <lc****@gmail.com> wrote in message
news:11**********************@f14g2000cwb.googlegr oups.com...

This might be more appropriate here. I'm new to C++, coming from a
background in another languages that allowed a similar solution to work
(Python). I wrote the following code in C++ based on the Python code
found here:

http://aspn.activestate.com/ASPN/Coo.../Recipe/302478 .... void looper(vector <vector<int> > nseq, vector<int> comb); First of all, in C++, when you pass parameters by value (as above),
a copy of the whole collection of items is created at each call.
Do get the equivalent of what Python does, you should pass
(large) parameters by reference:
void looper(vector< vector<int> > const& nseq, vector<int> comb);

Then, the efficient C++ equivalent of passing a sub-rage of a
collection, like "seqin[1:]" does in Python, is to pass a pair
if iterators within the collection.

From a quick read of the article, a C++ equivalent of the
"combine" function could be written as follows:
(Warning: quickly typed, not tested)
typedef vector<int> VI;
typedef vector<VI> VVI;

// the recursively called function
void combine( VVI::const_iterator i_begin
, VVI::const_iterator i_end
, VI& curBase, VVI& destination )
{
VI const& src = *i_begin;
++i_begin;
curBase.push_back(0); // add placeholder last item
for( VI::const_iterator scan=src.begin()
; scan != src.end() ; ++scan )
{
curBase.back() = *scan;
if( i_begin==i_end )
destination.push_back( curBase );
else
combine(i_begin,i_end,curBase,destination);
}
curBase.pop_back();
}

// the top-level function
VVI combine( VVI const& src )
{
VVI result;
VI base;
combine( src.begin(), src.end(), base, result );
return result;
}

It seems vectors can't be passed effectively as parameters to recursive
functions (at least how I'm doing it). Is this true?

Yes, at least how you were doing it.
The code above should work better, although it does
leave room for optimization.
I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[simont]

I think at least one of the arguments to looper is supposed to be an
out-argument, so it needs to be a non-const ref.

Besides, all this copying of sequences is expensive, when you could use
the std::algorithm idiom of pairs of iterators in your recursion. This
is loosely equivalent to passing seq[begin:end] in Python, which
refcounts rather than copies the storage iiuc.

Try this (works for me):
#include <vector>
#include <utility>
#include <iostream>

// might as well make it easy to use different containers for our
// algorithm: now we only need to change one line and the rest should
// still work (if we write it correctly). We're calling the list of
// arguments a Sequence, the output list of combinations can also be a
// Sequence, and the individual tuples in the input, and nested lists
// in the output, can both be 'Tuple's.
//
typedef int ValueT;
typedef std::vector<ValueT> Tuple;
typedef std::vector<Tuple> Sequence;

// we're going to do this using iterators instead of whole containers,
// so these typedefs will make it easy on the eye
typedef Tuple::const_iterator InputVal;
typedef Sequence::const_iterator InputIter;
typedef std::pair<InputIter,InputIter> SubSequence;

// note the use of non-const refs for out-parameters. We're passing
// the SubSequence by value, because it is cheap to copy
void looper( const SubSequence& inseq, // = seqin
Sequence& completed, // = listout
Tuple& current ) // = comb
{
if(inseq.first != inseq.second) { // = if seqin:
InputIter first = inseq.first;
const Tuple& curTuple = *first;
SubSequence recSeq(++first, inseq.second);
// calc seqin[1:] in advance, and we just avoided copying
// anything :-)

for(InputVal i = curTuple.begin(); i != curTuple.end(); ++i) {
// rather than create a new current combination each call,
// we just modify the existing one
current.push_back(*i);
looper(recSeq,completed,current);
// ~= rloop(seqin[1:],listout,newcomb)
current.pop_back();
}
} else {
// this does make a copy,
// but we've avoided the intermediate ones
completed.push_back(current);
}
}

// we can provide overloads for convenience here
void looper( const SubSequence& inseq, Sequence& completed )
{
Tuple scratch;
looper(inseq,completed,scratch);
}

void looper( const Sequence& inseq, Sequence& outseq )
{
looper( SubSequence(inseq.begin(),inseq.end()), outseq );
}

int main()
{
std::cout << "Enter constant tuple size: ";
int tupleSize;
std::cin >> tupleSize;

std::cout << "Enter number of tuples: ";
int numTuples;
std::cin >> numTuples;

Sequence inseq(numTuples);
for(int i=0; i<numTuples; ++i) {
for(int j=0; j<tupleSize; ++j) {
inseq[i].push_back(j);
}
}

Sequence outseq;
looper(inseq,outseq);

std::cout << "Output =\n[\n";
for(int k=0; k<outseq.size(); ++k) {
std::cout << " [ ";
for(int l=0; l<numTuples; ++l) {
std::cout << outseq[k][l] << ", ";
}
std::cout << "],\n";
}
std::cout << "]\n";
}

[Jeff Schwab]

simont wrote:

I think at least one of the arguments to looper is supposed to be an
out-argument, so it needs to be a non-const ref.

Besides, all this copying of sequences is expensive, when you could use
the std::algorithm idiom of pairs of iterators in your recursion. This
is loosely equivalent to passing seq[begin:end] in Python, which
refcounts rather than copies the storage iiuc.

Try this (works for me):
#include <vector>
#include <utility>
#include <iostream>

// might as well make it easy to use different containers for our
// algorithm: now we only need to change one line and the rest should
// still work (if we write it correctly). We're calling the list of
// arguments a Sequence, the output list of combinations can also be a
// Sequence, and the individual tuples in the input, and nested lists
// in the output, can both be 'Tuple's.
//
typedef int ValueT;
typedef std::vector<ValueT> Tuple;
typedef std::vector<Tuple> Sequence;
<snip> commented code </>

If the type of the container is to be flexible, it is probably best to
avoid numeric indexing and calls to Sequence::size() like those in the
loop below. For example, std::list does not have an overloaded operator
[], and calls to std::list::size() may be O(n).
for(int k=0; k<outseq.size(); ++k) {
std::cout << " [ ";
for(int l=0; l<numTuples; ++l) {
std::cout << outseq[k][l] << ", ";
}
std::cout << "],\n";
}
std::cout << "]\n";
}