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!!
CodePudding user response:
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.