Permutating a vector

Question

I am trying to get every permutation of a vector but also with a divider that indicates sub-permutations. It seems there is a mistake in my code as you can see from my results the ending permutation.

0 1 3 2 | and 0 2 3 1 | and 0 3 2 1 | are all duplicated.

I am also curious if there is a way to do what I am trying to do that can accept a reference to the vector rather than making a copy.

IDEONE: http://ideone.com/fork/2v0wk3

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

void permute(vector<int> v, int path_length) {
    do {
        for(int i=0; i<=3; ++i) {
            cout << v[i] << " ";
            if(i == path_length-1)
            cout << "| ";
        }
        cout << endl;

        if(path_length == v.size()) {
            cout << "====="<< endl;
            return;
        }

        permute(v, path_length+1);
    } while(next_permutation(v.begin()+path_length-1,v.end()));
}

int main() {
    vector<int> v;

    for(int i=0;i<=3;++i)
        v.push_back(i);

    int path_length = 2;
    permute(v, path_length);
    return 0;
}

Results:

0 1 | 2 3 
0 1 2 | 3 
0 1 2 3 | 
=====
0 1 3 | 2 
0 1 3 2 | 
=====
0 1 | 3 2 
0 1 3 | 2 
0 1 3 2 | 
=====
0 2 | 1 3 
0 2 1 | 3 
0 2 1 3 | 
=====
0 2 3 | 1 
0 2 3 1 | 
=====
0 2 | 3 1 
0 2 3 | 1 
0 2 3 1 | 
=====
0 3 | 1 2 
0 3 1 | 2 
0 3 1 2 | 
=====
0 3 2 | 1 
0 3 2 1 | 
=====
0 3 | 2 1 
0 3 2 | 1 
0 3 2 1 | 
=====

Expected Results:

0 1 | 2 3 
0 1 2 | 3 
0 1 2 3 | 
=====
0 1 3 | 2 
0 1 3 2 | 
=====
0 2 | 1 3 
0 2 1 | 3 
0 2 1 3 | 
=====
0 2 3 | 1 
0 2 3 1 | 
=====
0 3 | 1 2 
0 3 1 | 2 
0 3 1 2 | 
=====
0 3 2 | 1 
0 3 2 1 | 
=====

Answer 1

Consider another way to generate every sequence you need. We will have a vector <int> cur to store the current sequence, and a vector <bool> used to track which integers are used and which are not. In a recursive function with a depth argument, find another unused integer, put it as cur[depth] and proceed considering the next position, which is depth + 1. Print the result anytime the depth is in the required bounds.

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

int const n = 3;

void generate (vector <int> & cur, vector <bool> & used, int depth) {
    if (depth >= 2) {
        for (int i = 0; i < depth; i++) {
            cout << cur[i] << ' ';
        }
        cout << endl;
    }
    for (int i = 0; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            cur[depth] = i;
            generate (cur, used, depth + 1);
            used[i] = false;
        }
    }
}

int main () {
    vector <int> cur (n);
    vector <bool> used (n, false);
    cur[0] = 0;
    used[0] = true;
    generate (cur, used, 1);
    return 0;
}

And the output is:

0 1 
0 1 2 
0 1 2 3 
0 1 3 
0 1 3 2 
0 2 
0 2 1 
0 2 1 3 
0 2 3 
0 2 3 1 
0 3 
0 3 1 
0 3 1 2 
0 3 2 
0 3 2 1 

You can add the ===== part, too, if you print it when depth > n.

Answer 2

Your question is not very clear to me. You can use the not so well known next permutation from the STL :

std::vector<int> my_vector = { 1 , 5 , 7 , 2 , 3 , 10};
std::sort(my_vector.begin(), my_vector.end());
do {
    std::copy(my_vector.begin(), my_vector.end(), ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
} while(std::next_permutation(my_vector.begin(), my_vector.end()));

1 - Sort the vector 2 - Iterate over the permutations (the do while just print it with a copy to the cout)

I'm not wure of what you call "sub" permutations, are you just moving the "|" inside each permutation ?