字符串向量的 next_permutation 跳过一个排列

Question

我正在尝试打印字符串向量的所有排列。此代码按预期工作：

#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()));
}

输出：

+1 x4
x4 +1

但是当我将“x4”更改为“*4”时，next_pemutation 循环只迭代一次。

#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()));
}

输出：

+1 *4

其他字符如 # 似乎具有相同的效果。为什么会发生？

Answer 1

您的算法需要从 sortedvector开始打印所有排列：

"+1" < "x4"( '+' < 'x'): 所以你真的从“第一个”排列开始。
"+1" > "*4"( '+' > '*'): 所以你不会从第一个排列开始。

参见 man ascii 的顺序char（ascii 是最流行的一种，但平台可以使用其他作为 EBCDIC）。

要解决您的问题，您可以在最后一个之后执行push_back：

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