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;

    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++){

    return q;

int main(){

    return 0;
4 Years
Discussion Span
Last Post by osiron

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 by osiron: Typo

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.