如何实现类似std::next_permutation且无需用完字符串所有字符的排列组合？

AI 小北

2026-9-24

问题解答

C++标准库没有提供直接实现该需求的内置方法，你可以结合现有标准库的next_permutation和位掩码枚举的方式快速实现。

实现思路

枚举所有非空的字符选择状态：用位掩码标记当前选中原字符串中的哪些字符，覆盖所有长度1到原字符串长度的选择场景
对每个选中的字符子集，生成全排列后存入结果
额外去重避免原字符串存在重复字符时生成重复结果

参考实现代码

#include <string>
#include <vector>
#include <algorithm>
#include <set>

void get_all_permutations(std::string s, std::vector<std::string>& res) {
    int n = s.size();
    std::set<std::string> unique_res; // 自动去重

    // 枚举所有非空子集
    for (int mask = 1; mask < (1 << n); ++mask) {
        std::string cur;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                cur.push_back(s[i]);
            }
        }
        // 对当前子集生成全排列
        std::sort(cur.begin(), cur.end());
        do {
            unique_res.insert(cur);
        } while (std::next_permutation(cur.begin(), cur.end()));
    }

    // 转存到结果vector
    res.assign(unique_res.begin(), unique_res.end());
}