題目鏈接：

全排列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

方法一 遞歸：

思路：

1. 定義遞歸函數 generatePermutations，其中參數 prefix 表示當前已生成的前綴，參數 remaining 表示剩余的字符。
2. 如果剩余字符串只有一個字符，將前綴和剩余字符拼接輸出。
3. 否則，遍歷剩余字符，分別將當前字符作為前綴的一部分，然后遞歸調用生成剩余部分的全排列。
4. 在 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;
}

提交結果：

?