题目描述

有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段，原地发现n个断口整齐的石碑碎片。

为了破解石碑内容，考古学家希望有程序能帮忙计算复原后的石碑文字组合数，你能帮忙吗？

输入描述

第一行输入一个整数 n，表示石碑碎片的个数。

第二行输入n个字符串，表示n个石碑碎片的内容，每个字符串之间有空格。

输出描述

输出石碑文字的所有组合（按照升序排列），每个组合占一行。

如果存在石碑碎片内容完全相同，则由于碎片间的顺序变换不影响复原后的碑文内容，即相同碎片间的位置变换不影响组合。

用例输入

3 
a b c

abc 
acb 
bac 
bca 
cab 
cba

3 
a b a

aab 
aba 
baa

3 
a b ab

aabb 
abab 
abba 
baab 
baba

解题思路

1. 输入数据处理：

   • 读取输入的整数 n 和 n 个碎片字符串。

2. 排列生成：

   • 使用 全排列 来生成所有碎片的排列组合。
   • 对碎片进行排序，确保排列是按字典序生成的。

3. 去重：

   • 利用 next_permutation 可以生成当前序列的下一个排列，确保不重复地生成所有排列。

4. 输出处理：

   • 将每一种排列的结果拼接成一个字符串，并将所有排列按照顺序输出。

5. 实现技巧：

   • 使用 next_permutation 生成排列，并通过排序保证结果按字典序排列。

代码

#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <algorithm>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<string> fragments(n);for (int i = 0; i < n; i++) {cin >> fragments[i];}// 对碎片进行排序，保证生成的排列是按字典序的sort(fragments.begin(), fragments.end());// 用来存储所有的排列结果vector<string> result;// 使用next_permutation生成所有排列do {string combined = "";for (int i = 0; i < n; i++) {combined += fragments[i];}result.push_back(combined);} while (next_permutation(fragments.begin(), fragments.end()));// 输出所有的排列，拼接成一个字符串输出for (const auto& s : result) {cout << s<<"\n";}
}