机试题——考古学家

题目描述

有一个考古学家发现一个石碑，但是很可惜，发现时其已经断成多段，原地发现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";
    }
}