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;

Recommended Answers

Here, this should help you.

Jump to Post

All 2 Replies

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.