C++ permutation using std::list produces infinite loop

Question

I'm trying to generate all permutations of a vector v using backtracking.
The basic idea of my algorithm is:
at each recursive step, iterate through the remaining elements of v, and pick one to add the resulting permutation. I then delete it from the vector v. I'm trying to speed up the deletion operation by using a std::list. However, this seems to produce an infinite recursive loop that outputs only the first possible permutation.
I can only suspect that it's some problem with my handling of the iterator, but I'm not sure how to fix it.

Here's my code below:

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

vector<int> res;
list<int> v = {1, 2, 3, 4};
void permute() {
    if (v.empty()) {
        for (int d : res) cout << d << " ";
        cout << endl;
        return;
    }
    for (auto it = v.begin(); it != v.end(); it ++) {
        int d = *it;
        res.push_back(d);
        it = v.erase(it);
        permute();
        v.insert(it, d);
        res.pop_back();
    }
}
int main() {
    permute();
}

This piece of code just prints "1 2 3 4" forever. Any help is appreciated. Thanks!!

Answer 1

The problem is here: v.insert(it, d);

You will need to insert the value d back where it was, but you are not doing it.

list is not suitable for what you're trying to do. Use a vector, and instead of deleting, use swaps.