Passing vectors as parameters to a recursive function

Discussion in 'C++' started by lugal, Mar 23, 2005.

  1. lugal

    lugal Guest

    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/Cookbook/Python/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);
    looper(gseq, tcomb);
    }
    } else {
    master.push_back(comb);
    }
    }

    // end

    The program dies on the line:

    tcomb.push_back(tseq);

    It seems vectors can't be passed effectively as parameters to recursive
    functions (at least how I'm doing it). Is this true?
    lugal, Mar 23, 2005
    #1
    1. Advertising

  2. 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);
    > 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
    Bogdan Sintoma, Mar 23, 2005
    #2
    1. Advertising

  3. lugal

    Jeff Schwab Guest

    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/Cookbook/Python/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);
    looper(gseq, tcomb);
    }
    }
    else {
    master.push_back(comb);
    }
    }

    // end
    Jeff Schwab, Mar 23, 2005
    #3
  4. "lugal" <> wrote in message
    news:...
    > 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/Cookbook/Python/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
    Ivan Vecerina, Mar 23, 2005
    #4
  5. lugal

    simont Guest

    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.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";
    }
    simont, Mar 23, 2005
    #5
  6. lugal

    Jeff Schwab Guest

    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";
    > }
    Jeff Schwab, Mar 23, 2005
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page