Working on a small program recently I found a quirk in next_permutation. The prorgam read a sequence of characters from the command line and then tried to find words by testing each permuation. For a sequence of 3 characters there are 6 permutations.
Most of the online examples look something like this:
vector<int> set {'a', 'b', 'c'};
do {
for (auto x : set)
cout << (char)x;
cout << endl;
} while (next_permutation(set.begin(), set.end()));Which produces:
abc
acb
bac
bca
cab
cba
No surprises but when I cam to process input like ‘bac’ the number of permutations found were far too small.
bac
bca
cab
qcba
The problem is that the next_permutation modifies or mutates the vector so it needs to have a state to know when it has completed. That state is the vector itself. next_permutation returns false when all the elements are in increasing order.
To work with arbitrary input the sequence first needs to be sorted.
set = {'b', 'a', 'c'};
sort(set.begin(), set.end());
do {
for (auto x : set)
cout << (char)x;
cout << endl;
} while (next_permutation(set.begin(), set.end()));which now produces the right result
abc
acb
bac
bca
cab
cba