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;
}
``````

## Recommended Answers

Here, this should help you.

## All 2 Replies

Here, this should help you.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.