如何用C++生成长度≤原字符串的字符串排列？

嘿，我明白你想要的是不仅能生成原字符串长度的全排列，还能输出所有更短长度的排列结果对吧？刚好我整理了一个完整的实现方案，咱们一步步来看：

核心思路 #

要实现这个需求，咱们得拆成两步走：

• 第一步：从原字符串中选出所有长度为k（1 ≤ k ≤ 原字符串长度）的不重复子序列（如果原字符串有重复字符，得避免选到完全一样的子序列）
• 第二步：对每个选出的子序列，生成它的所有全排列，同样要处理重复字符的情况，避免输出重复结果

完整实现代码 #

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

using namespace std;

// 生成所有长度为k的不重复子序列
void generateSubsequences(const string& str, int start, int k, string current, set<string>& subs) {
    if (current.size() == k) {
        subs.insert(current);
        return;
    }
    for (int i = start; i < str.size(); ++i) {
        // 跳过重复字符，避免生成重复子序列
        if (i > start && str[i] == str[i-1]) {
            continue;
        }
        generateSubsequences(str, i + 1, k, current + str[i], subs);
    }
}

int main() {
    string str;
    cout << "Enter the string : ";
    cin >> str;
    
    // 先排序原字符串，方便后续去重处理
    sort(str.begin(), str.end());
    
    int n = str.size();
    // 遍历所有可能的子排列长度：1到n
    for (int k = 1; k <= n; ++k) {
        set<string> subsequences;
        generateSubsequences(str, 0, k, "", subsequences);
        
        cout << "\n=== 长度为" << k << "的排列 ===" << endl;
        // 对每个子序列生成全排列
        for (const string& sub : subsequences) {
            string temp = sub;
            do {
                cout << temp << endl;
            } while (next_permutation(temp.begin(), temp.end()));
        }
    }
    
    return 0;
}

代码关键细节解释 #

1. 去重处理：
   • 先对原字符串排序，这样相同字符会挨在一起，方便后续跳过重复项
   • 在生成子序列时，跳过和前一个相同的字符（i > start && str[i] == str[i-1]），避免生成重复的子序列
   • 使用set<string>存储子序列，进一步确保不会有重复的子序列进入排列环节
2. 子序列生成：用递归回溯的方式，从原字符串中选择k个字符，每次选择后从下一个位置开始选，保证每个子序列的字符是按原排序后的顺序选取的（避免重复子序列）
3. 全排列生成：对每个子序列，用next_permutation生成所有可能的排列，因为子序列已经是排序后的，next_permutation会遍历所有不重复的排列

测试示例 #

比如输入dvoig，程序会输出：

• 长度1的排列：d、v、o、i、g
• 长度2的排列：dv、vd、do、od、di、id、dg、gd、vo、ov、vi、iv、vg、gv、oi、io、og、go、ig、gi
• ...以此类推，直到长度5的所有全排列（和你原来用next_permutation得到的结果一致）

如果输入有重复字符的字符串，比如aab，程序会自动去重，不会输出重复的排列（比如长度2的排列只会输出aa、ab、ba，不会重复输出aa）

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