[保研/考研机试] KY43 全排列北京大学复试上机题 C++实现

题目链接：

全排列https://www.nowcoder.com/share/jump/437195121692001512368

描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入描述：

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

输出描述：

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：已知S = s1s2...sk , T = t1t2...tk，则S < T 等价于，存在p (1 <= p <= k)，使得 s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。每组样例输出结束后要再输出一个回车。

示例1

输入：

abc

输出：

abc
acb
bac
bca
cab
cba

方法一递归：

思路：

定义递归函数 generatePermutations，其中参数 prefix 表示当前已生成的前缀，参数 remaining 表示剩余的字符。
如果剩余字符串只有一个字符，将前缀和剩余字符拼接输出。
否则，遍历剩余字符，分别将当前字符作为前缀的一部分，然后递归调用生成剩余部分的全排列。
在 main 函数中，读入输入的字符串，调用递归函数生成全排列。

源代码：

#include<iostream>
using namespace std;

// 递归函数，用于生成字符串的全排列
void generatePermutations(string prefix, string remaining) {
    if (remaining.size() == 1) {
        // 如果剩余字符串只有一个字符，将前缀和剩余字符拼接输出
        cout << prefix + remaining << endl;
        return;
    }
    // 遍历剩余字符，分别将当前字符作为前缀的一部分，继续递归生成全排列
    for (int i = 0; i < remaining.size(); i++) {
        string newPrefix = prefix + remaining[i]; // 当前字符作为前缀的一部分
        string newRemaining = remaining; // 拷贝剩余字符串
        newRemaining.erase(i, 1); // 删除当前字符，得到新的剩余字符串
        generatePermutations(newPrefix, newRemaining); // 递归调用生成全排列
    }
}

int main() {
    string s;
    cin >> s; // 输入字符串
    generatePermutations("", s); // 调用递归函数生成全排列

    return 0;
}

方法二使用内置全排列函数：

`next_permutation` 函数的作用：

next_permutation 是 C++ 标准库中的一个函数，用于生成给定序列的下一个排列，以字典序的方式。
如果当前排列是字典序的最后一个排列，next_permutation 返回 false，否则返回 true 并生成下一个排列。
在生成下一个排列时，会将当前排列修改为下一个排列。
next_permutation 函数接受两个迭代器作为参数，表示需要生成排列的范围。

源代码：

#include <iostream>
#include <algorithm> // 包含了 sort 和 next_permutation 函数
using namespace std;

int main() {
    string s;
    while (cin >> s) { // 循环读取输入的字符串
        cout << s << endl; // 输出初始字符串
        sort(s.begin(), s.end()); // 将字符串按照字典序排序

        // 使用 next_permutation 生成剩余的全排列并输出
        for (; next_permutation(s.begin(), s.end());) {
            cout << s << endl;
        }

        cout << endl; // 每组样例输出结束后输出一个回车
    }
    return 0;
}