recursive permutations using vector

Question

I have this function that is suppose to return all possible permutation of integers inside the vector. The code is based from an existing code that does a permutation of strings, I tried to remodeled it to work on vectors but apparently, they dont work similarly as I thought.. I'll appreciate any help that you could offer thanks;

vector<vector<int>> permute(vector<int> &v1, vector<int> &v2){
    vector<vector<int>> v;
    if( v1.empty() )
    {
        v.push_back(v2);
        return v;
    }
    for(auto it = v1.begin(); it != v1.end(); it++){
        vector<int> temp1 = v1;
        temp1.erase(it);          //there's a runtime error on this line
        vector<int> temp2 = v2;
        temp2.push_back(*it);

        permute(temp1, temp2);
    } 

    return v;
}

This is the original code that permutes a string.

void string_permutation( std::string& orig, std::string& perm )
    {
        if( orig.empty() )
        {
            std::cout<<perm<<std::endl;
            return;
        }

        for(int i=0;i<orig.size();++i)
        {
            std::string orig2 = orig;

            orig2.erase(i,1);

            std::string perm2 = perm;

            perm2 += orig.at(i);

            string_permutation(orig2,perm2);
        } 
    }

@PSIAlt ,Hi, Im sorry, I forgot to mention, I am not allowed to use any function in STL algorithm — XDProgrammer
– XDProgrammer, Commented Jun 19, 2015 at 19:52

Steephen · Accepted Answer · 2015-06-19 23:47:53Z

2

Here you go:

   template < typename T>
   void vec_permute( std::vector<T> &orig, std::vector<T> &perm)
   {
       if(orig.empty())
       {
            for( auto &x : perm)
                std::cout<<x;
            std::cout<<"\n";
            return;
       }
       for(typename std::vector<T>::size_type i=0;i <orig.size();++i)
       {
            std::vector<T> orig2(orig);
            orig2.erase(std::find(orig2.begin(),orig2.end(),orig.at(i)));
            std::vector<T> perm2(perm);
            perm2.push_back(orig.at(i));
            vec_permute(orig2,perm2);            
       }
   }

Demo: http://coliru.stacked-crooked.com/a/01ded4b778aa4165

answered Jun 19, 2015 at 23:47

Steephen

16k7 gold badges46 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

XDProgrammer Over a year ago

Hi thank for this code, I test it and work.. , apparently I am not allowed to use algorithm STL.. but this is really helpful, I will just remodeled , it accordingly.. thanks..

Glenn Teitelbaum · Accepted Answer · 2015-06-19 19:52:52Z

0

Iterators can only be used with the container that you instanciated them with

answered Jun 19, 2015 at 19:52

Glenn Teitelbaum

10.4k4 gold badges42 silver badges82 bronze badges

2 Comments

XDProgrammer Over a year ago

thanks for reply, is there another way to erase the element without using an iterators?

Glenn Teitelbaum Over a year ago

You can erase using temp.begin () + pos. So you can loop using int positions and erase that way

Collectives™ on Stack Overflow

recursive permutations using vector

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related