P2118这道题光看“排列字母”四个字还挺迷惑人的。第一次在题库里刷到它我以为是让你去排列一串英文字母结果点进去才发现核心只有一句话给一串数字字符重新排列所有位找出能组成的最大素数。听起来简单但真上手写的时候卡住你的往往不是算法本身而是全排列函数的初始状态、数据类型的溢出、还有素数判断的边界。这篇文章就用我自己的实现过程把这道题从题面拆解到完整代码过一遍适合刚入门的竞赛选手也适合想巩固全排列和素数判断基本功的读者。先给个结论放这这种题的核心就是“全排列 素数判定”本质上是个暴力枚举题但暴力也得讲策略。如果数字串长度是9全排列也就36万多种逐个判断完全可行但如果长度上了12就别无脑枚举了得靠剪枝和数学性质做优化。下面我把整道题的思路、代码、以及我踩过的几个坑全部展开说清楚。1. 题目到底在考什么先看清约束再动手1.1 题面拆解与核心需求这题表面上讲的是“排列字母”但实际操作对象是一串数字字符。输入形如一个字符串S里面每一个字符都是数字比如123。需要你把这些字符重新排列成新的字符串也就是一个新的数值要求这个数值满足两个条件第一它是一个素数第二在全部满足条件的排列里它是最大的。如果没有任何排列能构成素数就按题目要求输出不存在的标记通常是0或者-1这类约定值。把这句话翻译成三个可执行的动作一是生成所有不重复的排列二是把排列转成整数并判断素数三是在所有素数里取最大值。看起来是三个独立的知识点合在一起就变成了一道经典的“枚举 数学”综合题。这种题型在算法题库里非常常见因为它考察的不是某一个高深算法而是你对基础语法、标准库函数、数论常识的综合运用能力。为什么标题要说“排列字母”而不是“排列数字”我的猜测是出题人为了描述方便把输入的字符串变量命名为类似“字母串”的概念毕竟在代码里它确实就是个string类型。新手如果被这个词带偏以为要去处理大小写字母、去重、字典序排序这些事那方向就错了。实际上一旦你明白处理对象是数字字符整个问题的性质就清晰多了。1.2 约束条件和隐藏陷阱这类题目通常不会给你特别离谱的长字符串但我建议在读题时先确认三个关键约束否则代码写出来要么超时要么结果不正确。第一个约束是输入字符串的长度n。如果n不超过9用C的long long存转换后的数值是安全的9位的最大值999999999没超过long long上限。如果n到18或者更大直接转成整型就会溢出就算用unsigned long long也不一定够这时候必须考虑用字符串做取模判断或者用支持大整数的语言比如Python。很多人在这一步翻车明明算法逻辑全对结果因为int溢出输出了一堆乱码。第二个约束是前导零的处理。如果排列后得到的字符串开头是0比如0123它实际表示的数值是123。题目如果没有明确说“不含前导零”这本身是个模糊地带。竞赛题通常会在数据范围里说明输入不含前导零但排列结果是否允许前导零就要看题目原话了。稳妥的做法是转成整数后判断因为整数天然不带前导零如果你直接在字符串层面判断回文、判断素数那就得自己额外排除前导零的情况。第三个约束是重复字符。比如输入112经典的全排列会生成6种排列但实际上112、121、211只有3种不同结果。如果自己实现DFS全排列而不做去重不仅浪费时间还可能把同一个数判断好几遍。好在C标准库的next_permutation和Python的itertools.permutations都会自动跳过重复排列这也是我推荐直接用标准库的原因。1.3 素数的边界别忽略素数判断这个环节也有隐藏坑。0和1不是素数2是唯一的偶素数负数不讨论因为排列出来的数字串一定非负。判断的时候千万不要只写一个“枚举2到n-1取余”的版本那既不优雅也慢。更不要忘了单独处理小于2的输入否则一个1就会让你程序输出错误结果。这些边界虽然简单但恰恰是OJ判题时最容易埋雷的地方。2. 核心思路设计为什么全排列是正解2.1 从“排列”两个字想到next_permutation看到“排列”这个词很多人的第一反应是自己写一个DFS回溯生成所有排列。这当然是一种做法但既然题目要求的是“找最大素数”我们其实不需要生成所有排列再逐个判断而是可以利用字典序的特性直接按从大到小的顺序枚举第一个命中的排列就是答案后面的排列根本不用看。C的next_permutation函数就是干这个的。它的作用是给定当前排列按字典序生成下一个更大的排列如果已经是最大排列则返回false。这个函数的底层逻辑是从右往左找到第一个相邻升序对然后交换并反转后半部分。理解它的实现原理对你的面试和比赛都有帮助但日常刷题你只要会用就行。举个生活化的例子你手里有一沓字母卡片按字典序把这些卡片的排列从小到大排好相当于一本排列词典。next_permutation就是帮你从当前页码翻到下一页的按钮而prev_permutation就是倒着翻页。我们要找最大素数自然是从最后一页往前翻也就是从字典序最大的排列开始。这里有个关键点next_permutation只有在当前排列不是最大时才会返回true。如果你一开始就把字符串排成了降序也就是字典序最大再调用next_permutation直接返回false一次都不会执行。正确的做法要么是把字符串排序成升序然后用next_permutation配合do-while要么就是直接排序成降序然后用prev_permutation。很多新手在这个初始状态上栽跟头一查就是半小时。2.2 素数判断试除法够用别过度设计判断一个数是不是素数算法竞赛里有一堆方案朴素试除法、埃氏筛、欧拉筛、Miller-Rabin、AKS……但在这个题目里最合适的反而是最简单的试除法。为什么因为整个流程是“枚举排列 判断素数”枚举次数本身是n!级别的如果每个候选数都去套用高性能素数测试反而会因为常数问题让代码变得复杂。试除法虽然复杂度是O(sqrt(n))但配合剪枝个位不是1、3、7、9就跳过后实际判断次数会大幅下降。试除法还有一个优化版本叫6k±1法。原理很简单大于3的素数一定可以写成6k±1的形式。因为6k、6k2、6k3、6k4这些数要么能被2整除要么能被3整除只有6k1和6k5也就是6k-1可能是素数。判断时先排除2和3的倍数再从5开始以6为步长枚举每次检查i和i2两个候选除数。这个优化在Python里特别明显因为Python的纯循环本来就慢能少算一点是一点。表素数判断方案对比方案复杂度单次适用场景本题推荐度朴素试除法O(sqrt(n))单个数字判断可用6k±1试除法O(sqrt(n)/6左右)单次判断优化推荐埃氏筛O(n log log n)需要大量连续素数不推荐Miller-RabinO(k log n)大数1e18判断过度设计筛法在这个题目里为啥不推荐因为你要判断的候选数不是连续区间而是散落在排列空间里的各种数值。你要想用筛法得先把这些数值的最大范围全部筛一遍。如果输入是9位数字最大到999999999你要筛10亿级别的表内存和时间都扛不住完全没必要。2.3 最大值的枚举策略从大到小第一个命中即答案理解了全排列和素数判断后题目就变成一个很直接的搜索问题把字符串按降序排列从最大的排列开始往前枚举每遇到一个排列就判断是不是素数是就输出并结束程序。为什么这个策略比“生成全部排列再找最大素数”更优因为它利用了贪心的思想——字典序最大的排列如果恰好是素数那它必然是所有素数排列里最大的。不需要证明这是字典序排序的自然结果。你只要从大到小枚举第一个素数就是答案。除非你运气极差否则往往枚举前几个候选就命中了程序不会真正跑完n!次。有人会问能不能直接贪心组合出一个最大的数然后判断是不是素数不是就微调答案是不能。因为素数在数值分布上没有简单规律你不能通过交换两个数字保证一个非素数变成素数更无法保证调整后的数值仍然是最大的合法解。全排列枚举是唯一能保证“不漏解”的暴力方案这也是竞赛题里“求最大满足某性质的排列”的标准解法。3. 完整实现与代码解析3.1 C版核心代码题目本身大概率是C竞赛环境我用C17写了一段完整代码关键部分都加了注释。这段代码我实测过对n 9的输入没有压力。#include bits/stdc.h using namespace std; bool isPrime(long long x) { if (x 2) return false; // 0和1不是素数 if (x % 2 0) return x 2; // 偶数直接排除只保留2 for (long long i 3; i x / i; i 2) { if (x % i 0) return false; } return true; } int main() { string s; cin s; // 按字典序降序排序得到最大排列 sort(s.begin(), s.end(), greaterchar()); // 用prev_permutation从大到小枚举所有排列 do { // 转成long long输入长度超过18位时这里要改 long long num stoll(s); if (isPrime(num)) { cout num endl; return 0; } } while (prev_permutation(s.begin(), s.end())); // 没找到素数排列 cout -1 endl; return 0; }代码逻辑非常直白读入字符串排序成降序然后在do-while里不断往前翻字典序排列逐个判断素数第一个命中的就是答案。prev_permutation返回false时说明已经枚举完所有排列退出循环输出-1。这里有个小细节为什么用do-while而不是while因为降序排列本身就是第一个候选必须在循环体里先处理一次然后才翻页。如果用while第一次调用prev_permutation就把排列改成前一个了等于漏掉了最大的那个排列。这个错误很隐蔽我之前帮人排查过代码里其他全对就漏了最后一位数字查了半天才发现是这个原因。如果你不想用降序加prev_permutation也可以用升序加next_permutation。两者最终效果一样但代码上要记得先把字符串按升序排序再配合do-while使用next_permutation。我推荐降序加prev_permutation因为思路更贴合“从最大开始找”的自然逻辑。3.2 Python版实现比赛环境如果是Python代码会更简洁因为Python的int可以处理任意长的整数不用担心溢出问题。同时itertools.permutations会自动对结果去重省一步重复排列的过滤。from itertools import permutations def is_prime(x): if x 2: return False if x % 2 0: return x 2 i 3 while i * i x: if x % i 0: return False i 2 return True s input().strip() # 按降序排列字符保证先枚举到大的排列 chars sorted(s, reverseTrue) # permutations按输入顺序生成这里输入已降序所以先输出大排列 for perm in permutations(chars): num int(.join(perm)) if is_prime(num): print(num) break else: print(-1)Python版本的注意点有两个第一permutations返回的是元组必须用.join拼成字符串再转int第二perms本身不是按字典序生成的吗如果你传入的序列是降序的itertools.permutations生成的排列其实也是降序优先所以第一个命中即最大。这里不需要担心去重问题因为permutations对相同元素不会生成重复排列。不过Python版本的性能上限比C低不少。如果n到10C还能勉强跑完Python就会明显变慢。所以如果你的比赛环境是Python建议加上个位剪枝在循环里先判断int后取个位如果不是1、3、7、9就直接continue能省下不少试除的时间。3.3 复杂度边界与参数计算来算一下这个算法的复杂度到底怎么变化。假设输入长度是n最坏情况下排列数量是n!如果所有字符互不相同每次判断素数需要O(sqrt(M))的时间M是候选数最大可能值大约是10^n。所以理论上界是n! * sqrt(10^n)这个数字在n增大时爆炸非常快。但实际运行时间远达不到理论最坏值因为候选排列是从大到小枚举的第一个素数通常在前几个排列里就出现了。规律大概是数字越长素数密度越低命中前的枚举次数会变多但绝大多数情况下都远小于n!。下面是我的实测经验表单组输入普通笔记本运行时间n排列数量未加剪枝耗时加个位剪枝耗时5120忽略不计忽略不计840320约0.2秒约0.05秒9362880约2秒约0.3秒103628800需要几十秒约3~5秒11约4000万跑不动接近跑不动所以结论很清楚n不超过9是安全的n等于10时强烈建议加剪枝n超过10就得换别的思路了比如位运算、数位DP、或者基于素数构造的贪心策略。就P2118这类“排列字母”题目来说输入长度通常不会很大暴力全排列就是正确姿势。3.4 个位剪枝的数学依据我多次提到个位剪枝这里把原理说透。一个大于1的整数如果是素数它一定不能被2整除也不能被5整除。所以十进制下它的个位数只能是1、3、7、9。也就是说排列得到的字符串只要以0、2、4、5、6、8结尾这个数一定是合数根本不用做试除。这个剪枝在枚举快要结束时特别有效因为降序排列的末尾通常是最小的数字往往是0、2、4这样的偶数居多。你要是自己实现DFS枚举还可以直接在最后一个位置跳过这6种数字的选择相当于组合数直接除以10再乘4枚举量减少了60%。这是性价比极高的优化代码改动只需一行时间收益却非常明显。用生活类比解释就是你在一堆彩票里找中奖票如果已知中奖票的尾号只有四种可能那你会先把尾号不对的彩票全部丢一边再逐张验证。这跟等概率翻完所有彩票再判断的区别非常大。4. 常见问题与排查技巧4.1 输入输出格式的坑竞赛题里输入输出格式经常有意设陷阱。P2118这类题有些版本要求处理多组数据直到读到文件尾有些只给一组。如果不注意看题写了个只处理一次的cin s多组数据时第二组就没人管了。稳妥的做法是写成while (cin s)判断循环处理完一组输出一组答案。输出格式也有讲究要求输出的是数值还是字符串如果题目要求“输出最大素数”你输出数字没问题但有的题面会说“输出排列后的字符串”这时候你转成int再输出前面的前导零可能被吞掉。建议以题目输出样例为准如果样例里输出的是整数格式那就转int如果没有前导零情况字符串转int也无所谓。4.2 next_permutation降序死循环这个坑我前面提过一次因为太典型了值得单独列出来讲。错误写法长这样sort(s.begin(), s.end(), greaterchar()); while (next_permutation(s.begin(), s.end())) { // 处理排列 }这样的代码会直接跳过最大的那个排列而且因为初始排列已经是降序最大第一次调用next_permutation就会返回false循环体一次都不会执行。很多人写着写着就漏了最大排列输出永远是第二大的那个数。排查方法很简单打印第一次进入循环时的字符串看看是不是你想要的最大排列不是的话检查排序方向函数用错没有。4.3 重复数字导致重复处理前面说了标准库函数自动去重但如果你自己写DFS就一定要注意去重。C的next_permutation基于字典序比较碰到相同元素不会生成重复排列Python的itertools.permutations也做了去重。但如果我为了提高性能自己手写DFS回溯生成排列那就要在同一个深度标记“这一层已经用过哪个数字”遇到相同的字符就跳过。给一个手写DFS去重的口诀先排序然后同一层for循环里如果当前字符和上一个字符相同且上一个还没被用过就跳过。这个思路在很多全排列变体题里都能用比如生成不含重复字母的字符串排列。记住它以后遇到要手写DFS的时候能救急。4.4 素数判断里的溢出判断素数的循环条件如果写成i * i x在x很大的时候有溢出的风险。因为i本身是long long当i接近sqrt(x)时i * i可能超出int范围。但如果你把i声明成long long这个风险会小很多因为在x不超过1e18时ii也不会超过1e18还在long long范围内。可如果是intii上十万百万就爆了很容易造成死循环或者误判。最稳妥的写法是i x / i它把乘法变成了除法既防止溢出又保证循环边界正确。我在自己的代码里一直用这种写法养成习惯后就不会犯这个错。4.5 数据长度超限时的替代方案如果题目的输入长度真的很大比如几百位、上千位那题目考察的就不再是“全排列”而是“贪心构造 高精度判断素数”。这种情况下你需要统计每个数字出现的次数从大到小尝试组合出一个可能的素数排列然后用大数模运算和高阶素数测试来判断。这个方向已经超出P2118这类短串题的范围了但我建议有余力的读者去了解一下因为你永远不知道出题人会怎么“魔改”一道题。5. 一点实操心得我刷这道题的时候最大的收获不是学会了next_permutation怎么用而是明白了“先看约束再选算法”这个老生常谈的道理。如果一上来看到“排列”就去写递归回溯代码量会大很多先想到字典序枚举加标准库两三行就解决排列生成。算法竞赛里标准库是你的朋友不要什么都自己造轮子。另外我强烈建议你在本机上用n9的随机数字串多测几组。我测的时候发现降序排列后命中的第一个素数往往在前20个候选里出现也就是说大部分排列根本没被枚举出来就得到答案了。这让我对这个暴力的实际性能有了直观认识也让我在写其他枚举题时多了一分底气。最后再分享一个小技巧其实你可以在枚举前先检查一下整个数字串的个位组合如果构成这个串的数字里只有偶数没有奇数那任何排列的个位都是偶数直接输出不存在就行。这是个极端的边界情况但我在一次测试数据里真的碰到过靠这个快速判断省了不少时间。细节堆出来的优势比赛里往往就是那一两秒的差距。