C++全排列函数std::next_permutation的陷阱与优化

1. 从洛谷P1603看全排列的陷阱

第一次在洛谷P1603遇到全排列问题时，我像大多数初学者一样直接使用了C++标准库中的std::next_permutation函数。提交代码后却意外发现有几个测试用例无法通过——系统提示"缺失排列"。这个结果让我困惑不已，因为从文档上看这个函数应该能生成所有可能的排列组合。

经过仔细排查，我发现问题出在输入数据的预处理上。题目要求对字符串"Snowden"中的字母进行排列组合，而我直接将其转换为小写后传入函数：

cpp复制string s = "Snowden";
transform(s.begin(), s.end(), s.begin(), ::tolower);
sort(s.begin(), s.end());
do {
    // 处理排列
} while (next_permutation(s.begin(), s.end()));

这里隐藏着一个关键细节：std::next_permutation严格按照字典序生成排列，而原始字符串中包含重复字母'd'和'n'。当存在重复元素时，函数会自动跳过重复的排列组合——这正是导致"缺失排列"假象的根本原因。

2. std::next_permutation的运作机制

2.1 字典序排列的生成算法

std::next_permutation实现的是经典的Narayana算法，其核心步骤如下：

1. 从序列末尾向前查找第一个相邻升序对(i, i+1)，满足a_i < a_(i+1)
2. 如果找不到这样的对，说明整个序列已是逆序，排列结束
3. 从末尾向前查找第一个大于a_i的元素a_j
4. 交换a_i和a_j
5. 反转从i+1到末尾的子序列

这个算法的时间复杂度为O(n)，空间复杂度O(1)。对于包含重复元素的序列，算法在步骤3中会自动跳过那些会导致重复排列的交换操作。

2.2 重复元素的特殊处理

当序列中存在重复元素时，std::next_permutation的行为会发生变化。以字符串"aabb"为例：

1. 初始排序后得到"aabb"
2. 第一轮排列："aabb" → "abab" → "abba" → "baab" → "baba" → "bbaa"
3. 共6种排列，而非4!