I'm trying to create a program where I want to generate all permutations [1,2,3,4] and I recursively generate all the permutations of [1,2,3]:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

and then put 4 back into the sequence of numbers. For example, with [1,2,3], we get [4,1,2,3], [1,4,2,3], [1,2,4,3], and [1,2,3,4]. We "interleave" 4 with the sequence [1,2,3].

The following code shows the interleave and permute function. I'm currently stuck at the permute function where it returns a vector that contains all permutations of the first n positive integers and it is recursive: it generates all permutations of 1 upto n-1, apply interleave to each of the permutations and put all the resulting permutations into a vector. This vector then conatins all permutations of 1 upto n.

Is there a way to permute the numbers and do it recursively without using the next_permutation STL algorithm as I'm not allowed? Any help would be appriciated.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int> > interleave(int x, const vector<int>& v){

    vector<int> p(v.size()+1);
    vector<vector<int> > q(v.size()+1);

    for(vector<int>::size_type i = 0; i < p.size(); i++) {
        p = v;
        p.insert(p.begin()+i,x);
        q.push_back(p);
    }

    return q;

}

vector<vector<int> > permute(size_t n){

    vector<int> p;
    vector<vector<int> > q;


    if(n == 0){
        return q;
    }
    for(size_t i = 1; i < n; i++){
        p.push_back(i);
    }



    return q;
}   

int main(){

    permute(4);
    return 0;
}

Thanks, but is there any way to implement this using what I have? I know that you want me to code before giving me the solution but I really need help right now and the link that was given to me above didn't quite solve it.

Edited 4 Years Ago by osiron: Typo

This article has been dead for over six months. Start a new discussion instead.