如何实现字符串全排列算法？自定义递归代码运行异常求排查

一、std::next_permutation 底层实现逻辑 #

std::next_permutation 的核心是生成当前序列的下一个字典序排列，若当前已是最大字典序（完全降序），则返回false并将序列转为最小字典序（完全升序）。具体步骤如下：

1. 从后向前查找最长非递增后缀：找到第一个位置 i，满足 str[i] < str[i+1]，该位置即为需要交换的基准点。
2. 从后向前查找第一个大于str[i]的元素：找到位置 j，满足 str[j] > str[i]，交换 str[i] 和 str[j]。
3. 反转基准点后的后缀：将 i+1 到末尾的元素反转，得到下一个字典序排列。

举个例子，序列 "abcde" 生成下一个排列的过程：

• 最长非递增后缀是 "e"，找到i=3（str[3]='d' < str[4]='e'）
• 找到j=4，交换后得到 "abced"
• 反转i+1到末尾（仅"e"，无变化），最终结果为 "abced"

若输入序列是 "edcba"，找不到符合条件的i，则返回false，并将序列转为 "abcde"。

二、你的递归全排列代码问题分析 #

你的递归代码能生成全排列，但存在两个核心问题：

1. 无意义的回溯操作：permute 函数的参数是string str（值传递），每次调用都会拷贝字符串。递归前后的swap操作仅作用于拷贝的副本，回溯对原字符串无影响——这虽不影响生成排列，但属于无效操作。
2. 无法处理重复字符：若输入字符串包含重复字符（如 "aab"），代码会多次交换相同字符，导致输出重复的排列结果。例如输入 "aab" 时，会重复输出 "aab"、"aba"、"baa"。

三、修正后的全排列实现 #

版本1：去重的递归全排列（可选字典序） #

要解决重复问题，需在交换前判断当前字符是否已处理过，避免重复交换。若需要按字典序输出，先对字符串排序即可：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void permute(string str, int l, int r) {
    if (l == r) {
        cout << str << endl;
        return;
    }

    string used;
    for (int i = l; i <= r; i++) {
        // 跳过已处理过的字符，避免重复排列
        if (used.find(str[i]) != string::npos) {
            continue;
        }
        used.push_back(str[i]);

        swap(str[l], str[i]);
        permute(str, l + 1, r);
        swap(str[l], str[i]); // 值传递下此回溯无实际作用，仅保持代码习惯
    }
}

int main() {
    string str;
    cin >> str;
    // 排序后可按字典序输出排列
    sort(str.begin(), str.end());
    permute(str, 0, str.size() - 1);
    return 0;
}

输入 "aab" 时，输出无重复的排列：

aab
aba
baa

版本2：模拟std::next_permutation的非递归实现（字典序+去重） #

若要和标准库函数行为完全一致，可手动实现其逻辑：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool my_next_permutation(string& str) {
    int n = str.size();
    if (n <= 1) return false;

    // 步骤1：找最长非递增后缀的前一个位置i
    int i = n - 2;
    while (i >= 0 && str[i] >= str[i+1]) {
        i--;
    }

    // 若i<0，说明是最大排列，转为最小排列并返回false
    if (i < 0) {
        reverse(str.begin(), str.end());
        return false;
    }

    // 步骤2：找第一个大于str[i]的元素j
    int j = n - 1;
    while (str[j] <= str[i]) {
        j--;
    }

    // 步骤3：交换i和j，反转i+1到末尾
    swap(str[i], str[j]);
    reverse(str.begin() + i + 1, str.end());
    return true;
}

int main() {
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    cout << str << endl;
    while (my_next_permutation(str)) {
        cout << str << endl;
    }
    return 0;
}

该实现自动处理重复字符，生成的排列顺序和std::next_permutation完全一致。

四、补充优化 #

递归版本可改为引用传递（string& str）减少拷贝开销，此时回溯的swap是必须的，用于恢复原序列：

void permute(string& str, int l, int r) {
    if (l == r) {
        cout << str << endl;
        return;
    }

    string used;
    for (int i = l; i <= r; i++) {
        if (used.find(str[i]) != string::npos) continue;
        used.push_back(str[i]);

        swap(str[l], str[i]);
        permute(str, l + 1, r);
        swap(str[l], str[i]); // 引用传递下必须回溯，恢复原序列
    }
}

内容的提问来源于stack exchange，提问作者dgh