c++ - 字符串 vector 的 next_permutation 跳过一个排列

Question

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

#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

您的算法需要从排序的 vector 开始打印所有排列:

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

请参阅 man ascii 以获得 char 的顺序(ascii 是最流行的，但平台可以使用其他的作为 EBCDIC)。

要解决你的问题，你可以在最后push_back之后做:

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