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