next_permutation of vector of strings is skipping one permutation

Question

I'm trying to print all permutations of a vector of strings. This code works as intended:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    vector<string> v;

    v.push_back("+1");
    v.push_back("x4");

    do {
        cout << v[0] << " " << v[1] << endl;
    } while (next_permutation(v.begin(), v.end()));
}

Output:

+1 x4
x4 +1

But when I change "x4" for "*4" the next_pemutation loop iterates only one time.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    vector<string> v;

    v.push_back("+1");
    v.push_back("*4");

    do {
        cout << v[0] << " " << v[1] << endl;
    } while (next_permutation(v.begin(), v.end()));
}

Output:

+1 *4

Other characters like # seems to have the same effect. Why is it happening?

Answer 1

Your algorithm needs to start with a sorted vector to print all permutations:

"+1" < "x4" ('+' < 'x'): so you really begin with the "first" permutation.
"+1" > "*4" ('+' > '*'): So you don't begin with the first permutation.

See man ascii to have the order of char (ascii is the most popular one, but platforms can use other as EBCDIC though).

To solve your problem, you may do after the last push_back:

std::sort(v.begin(), v.end());