CODEWITHSUNDEEP
c++algorithmrecursionvectorpermute
Bobbis
Bobbis

Reputation: 137

C++ - Permutation Function

I'm writing a permute function that creates a vector of ints from the n parameter and interleaves them, using recursion. I am getting a segmentation fault, but am having much trouble trying to get it to work. Here is my code:

void print(const vector<int>& v) 
{
    for (auto it = v.begin(); it != v.end(); ++it) 
    {
        cout << *it << ' ';
    }

    cout << endl;
}

vector<vector<int> > interleave(int x, const vector<int>& v) 
{
    size_t i;
    vector<vector<int> > results;

    for (i=0;i<=v.size();i++) 
    {
        vector<int> temp(v); 

        temp.insert(temp.begin()+i, x);
        results.push_back(temp);
    }

    return results;
}

vector<vector<int> > permute(size_t n) 
{
    size_t i, j;
    vector<vector<int> > v;
    auto vectors = permute(n-1);
    vector<vector<int> > results;
    for (j=0;vectors.size();j++) 
    {
        for (i=1;i<=n-1;i++) 
        {
            vectors[j].push_back(i);
        }
    }

    for (j=0;j<=vectors.size();j++) 
    {
        for (i=1;i<=n-1;i++) 
        {
            vector<vector<int> > temp = interleave(i,vectors[j]);
            results.insert(results.end(), temp.begin(), temp.end());
        }
    }

    return results;
}

int main(void) 
{
    size_t i;
    vector<vector<int> > results = permute(3);
    for (i=0;i<results.size();i++) 
    {
        print(results[i]);      
    }
}

Upvotes: 1

Views: 701

Answers (1)

P. Kouvarakis
P. Kouvarakis

Reputation: 1943

permute() is endlessly recursive: it will always call permute(n-1). Eventually that would cause stack overflow - not sure why you get a segmentation fault (perhaps there are other issues with the code).

Also:

for (j=0;vectors.size();j++) {

will never exit. You probably meant:

for (j=0;j<vectors.size();j++) {

Note the < vs <=. If j=vectors.size(), vectors[j] is accessing items out of bounds.

Upvotes: 3

Related Questions