强迫症整理圣手的字典序试炼（二）：第k小之章
我的室友阿整——江湖人称“整齐哥”——上一回用他那套“镜像分离·点名归位·定海神针”大法，轻松碾碎了第1小回文排列的试炼。可就在他准备给信纸裱框时，背面浮现的太极图和那句“找第k小”直接把他定在了原地，像一台突然蓝屏的精密仪器。
现在，他盯着那张挑不出半点排版毛病的信纸，瞳孔像失去焦距的镜头。空气凝固了整整十秒——对阿整来说，十秒够他把书架按索书号重排三遍。终于，他喉咙里挤出了一声近乎系统报错的叹息：
“他们……居然连落款字体大小都是正文的0.618倍，完美的黄金分割！”
我差点把薯条呛进鼻子里。“喂，关注点不应该是这任务的难度吗？人家要你找第k小啊！”
阿整缓缓转过头，眼神里混合着敬畏与恐惧：“你不懂。一个连字号比例都算到黄金分割的组织——难度是附赠的，秩序才是本体。”
一、冷静，以及分治
阿整拾起地上的马克笔，用酒精棉片擦了擦笔身，以笔帽的logo朝向正北的方式插回笔筒。他闭上眼，再睁开时，眼里的混乱已经被一种冰冷的秩序取代。
“第k小。”他合上牛皮笔记本“整齐宪法”，“不过是字典序树上的精准定位，本质上和整理书架没有区别。”
他转身在白板上画了起来——原字符串s，长度n，左半边长度m=n//2：“回文排列的结构是不变的。左半任意排列，中间可能夹一个奇点，右半是左半的镜像。和上次一样，右半边是赠品，不参与决策。”
他用笔帽敲了敲白板：“所以问题降维——要找到第k个回文排列，只需求出左半部分字符的第k个字典序排列。”
先统计左半部分每个字符的出现次数：
n = len(s)
half_len = n // 2
# 用数组统计左半部分字符频率（索引 0-25 对应 a-z）
cnt = [0] * 26
for ch in s[:half_len]:
cnt[ord(ch) - ord('a')] += 1
“字符可能重复，排列不可区分——这是一个多重集排列问题，不是简单的全排列。同样的字母，谁先谁后都长得一样，不能重复计数。” 阿整看了看我，又补了句：“说人话就是：‘aab’和’aab’哪怕交换两个a的位置，也只算同一种排列，不能重复数。”
接着，他在白板上写下：
给定字符多重集，求：该集合按字典序构成的第k个排列是什么？
然后重重画了个圈。
“真正的难点不在于算总数，而在于——” 他转过身，十指交叉，指节发出整齐的咔嗒声，“——怎么从零开始，一位一位地把第k小拼出来。”
“想象你面前是一棵巨大的字典树，每一条从根到叶子的路径就是一个排列，按字母顺序排好。你要找第k条路径。你不可能把整棵树画出来——排列数量随长度爆炸式增长，画完树宇宙都热寂了。”
他在白板上画了一个节点，分出几个分支。
“你要做的是：站在根节点，算一算第一条分支下面藏了多少条路径。如果k比这个数小，就钻进这个分支；如果k比这个数大，就减掉这个分支的数量，跳过去看下一条分支。一层一层往下走，每一步都知道该选哪个字母——走到叶子，答案自然就拼出来了。”
他放下笔，双手抱胸，左右手又各敲了四下。
“所以问题就拆成两步：一，怎么快速算出一个分支下面藏了多少条路径——也就是给定字符集还剩多少种排列；二，怎么沿着这棵树逐层往下钻——也就是每一步根据k决定选哪个字母、要不要跳到下一个分支。”
“第二步是通用框架，第一步——算排列数——有两种打法” 他在白板上画了一条分叉线，左边写"比例递推"，右边写"组合截断"。
二、比例递推——按比例切蛋糕
阿整盯着白板上的字典树，树枝画得整整齐齐，分叉角度完全一致。“第一种打法：比例递推。”他在白板左半边写下标题，“核心就一句话——你已经知道整块蛋糕有多大，就不用每次都重新称重，按比例切就行。”
写完之后他又退后两步，歪头端详了三秒，上前把“推”字的提手旁和右边的“隹”间距调大了0.5毫米。
“第一步，工欲善其事，必先利其器。” 排列数公式的核心是阶乘——先做好阶乘预计算，用空间换时间：
# 预计算阶乘表：fact[i] = i!，避免重复计算大数阶乘
fact = [1] * (half_len + 1)
for i in range(1, half_len + 1):
fact[i] = fact[i - 1] * i
“阶乘是排列数的基本粒子。提前算好，随用随取，避免重复劳动——重复计算是对CPU的侮辱，CPU也有尊严。”
接着是排列数公式，他写下一个内部函数calc_perms:
# 多重集排列数 = length! / (cnt₁! × cnt₂! × ...)
def calc_perms(length: int, counter: list) -> int:
res = fact[length]
for v in counter:
res //= fact[v]
return res
“分子把所有人的可能性全部摊开，分母把同种字符内部的重复排列干掉。整除一定成立——任何余数都是对秩序的亵渎。”
“如果总排列数都不到k，那就直接返回空字符串——就像发现书架上缺了一本绝版书，用镜子补上虚像。” 阿整在这里轻轻点了点头，仿佛在向自己致敬。
# 计算左半部分的所有可能排列数
total_perms = calc_perms(half_len, cnt)
# 如果总排列数都不够 k，直接返回空字符串（无解）
if k > total_perms:
return ""
接着，他在白板上画了一个巨大的圆，又用红笔从圆心画出几条辐射线，把圆切成几个扇形。
“高潮来了。”他压低声音，“把total_perms 个排列看作一整块大饼。现在要按第一个位置字母把它切块——a开头的、b开头的、c开头的……每一块的大小，就是‘以这个字母开头的排列数量’。”
“怎么切？不用重新拿公式算。”他用笔帽戳了戳饼图，“多重集排列有一个天然对称性：在所有排列里，每个位置上的字符出现机会是均等的。换句话说，第一个位置是c的概率，就是c的个数除以总长度。”
他在饼图旁边奋笔疾书：
c块的大小 = 总饼 × (cnt[c] / remaining_length)
“比例递推的灵魂。”他转过身，眼神里燃起一丝布道者的狂热，“不需要每次重新跑一遍 calc_perms。你已经知道总饼有多大，只要乘上这个字符的占比，就直接得到了这个分支的精确大小。而且这个除法——”
他深吸一口气，“——永远整除。你看，对称性的终极体现就是，连余数都被消灭了，干干净净。”
他舔了舔嘴唇，写下循环框架：
half = [] # 存放最终拼出来的左半部分
remaining_length = half_len # 还剩多少个位置要填
current_perms = total_perms # 当前剩余的总排列数，初始为整块饼
for i in range(half_len):
for j in range(26): # 按字典序，从a到z试探
if cnt[j] == 0:
continue
# 分支大小 = 当前总饼 × 字符占比
new_perms = current_perms * cnt[j] // remaining_length
if k <= new_perms:
# 第k个就在这个分支里！选定字母j
half.append(ascii_lowercase[j])
cnt[j] -= 1
remaining_length -= 1
current_perms = new_perms # 钻进分支
break
else:
# 不在这个分支，跳过整块饼
k -= new_perms # 减去这块饼，继续看下一个字母
他放下笔，语气里带着一丝克制的得意：“站在每个位置，用比例切出分支大小。k落在里面就钻进去，落在外面就跳过去，同时把k平移到新分支里。循环结束，half里就是第k小的左半排列。没有重复计算，每一步只有一次乘法一次除法。”
最后镜像合体——右半是左半的倒影，中间奇点有就供上，没有就留白：
left = ''.join(half)
mid = s[n // 2] if n % 2 else ''
return left + mid + left[::-1]
测试用例绿灯通过。阿整盯着屏幕，十指指尖两两相对，搭成一个对称的拱门。
“这个解法，我叫它‘蛋糕不用切两次’。你不需要知道世界上有多少种蛋糕，你只需要拿好刀，按比例切下去，k会自己掉进属于它的那一块。”
三、组合截断——或者叫“够用就行”
但阿整的强迫症不允许他只拥有一种解法。他盯着那段代码里的 current_perms = new_perms，眉头又拧起来，像看到书架上一本书的封面偏了0.3毫米。
“每次都要把上一轮的状态传递下来，像一个幽灵缠在手上。虽然没错，但不够干净。”他把键盘往前一推，“有没有更独立的方法？
他翻开“整齐宪法”，翻到排列数公式那一页——左半边是阶乘推导，右半边不知什么时候被他对称地补了一栏“组合视角”，两边工整得像镜像，连涂改痕迹都没有，仿佛他在用笔尖遵守某种排版宪法。
总排列数 = C(m, cnt[a]) × C(m-cnt[a], cnt[b]) × …
“一样的结果，换个角度。”他用笔尖戳着公式，像是在给每个字母分配坐标，“先从m个空位里选cnt[a]个位置放a，再从剩下的位置里选cnt[b]个放b，一层一层往下，直到所有字符分配完毕。这是组合数的连乘积——”
他顿了顿，瞳孔里闪过一道锐光，像是发现了某种被隐藏的对称性，“而且，组合数天生就是整数乘除——每一步乘一个数再除一个数，步步整除，干干净净。连阶乘表都不用提前准备！”
“更妙的是——”他把笔一横，“如果我只关心排列数是不是大于等于k，那中途就可以截断。一旦当前乘积已经 >= k，后面根本不用继续乘，直接返回k。因为知道‘这个分支够大’就够了，精确值毫无意义，宇宙不需要知道你能排出一亿种还是十亿种。”
他告诉我这叫“截断美学”——够用就停，多算一个字都是对内存的不忠。接着，他写下组合数函数，从第一行就开始贯彻这个美学：
def comb(n: int, m: int) -> int:
m = min(m, n - m) # 对称优化：C(n,m) = C(n, n-m)，选小的算
res = 1
for i in range(1, m + 1):
res = res * (n + 1 - i) // i
if res >= k: # 截断！精确值已经不重要了
return k
return res
“m = min(m, n-m)——组合数天生左右对称，选小的那半边算，循环次数最少。对称性从最小的细节抓起。”
他十指交叉，指节咔嗒作响：“常规组合数能算出天文数字，但我要的只是一个布尔问题的答案——‘这个分支够不够大’。够了就停，不浪费一个字长的内存。这叫对计算机的尊重。”
接着，基于组合数，他继续写下排列数函数 perm(sz)。思路一如既往地整洁：按字母顺序，从a到z，每个字母依次从剩余空位里认领自己的位置——每次乘一个组合数，全部乘完就是总排列数。
def perm(sz: int) -> int:
res = 1
for c in cnt:
if c == 0:
continue
res *= comb(sz, c) # 从当前空位中选c个位置给这个字母
if res >= k: # 截断！后面的不用算了
return k
sz -= c # 空位减少，交给下一个字母
return res
他顿了一下，像是在检查代码对齐情况：“每个字母独立挑位置，谁也不依赖谁。这是搭积木，不是切蛋糕——每一步都是干净的组合选择，不存在 current_perms 那个需要一路传递的幽灵。”
先用一次 perm 判断k是否超出总数：
if perm(half_len) < k:
return ""
然后就是逐位构造——对于左半部分的每一个待填位置，按a到z尝试每个字母：
假设这一位放j，先临时扣掉一个j 的配额，再调用 perm(剩余长度) 计算剩下位置的排列数。如果这个数 p >= k，说明第k个就在这个分支里，选它；否则 k -= p，恢复j的计数，继续试下一个字母。
“先扣，再算，够就定，不够就还。”他舔了舔嘴唇，指法精准得像在做显微手术：
half = [''] * half_len
for i in range(half_len):
for j in range(26):
if cnt[j] == 0:
continue
cnt[j] -= 1 # 先扣：假设这一位选 j
p = perm(half_len - i - 1) # 再算：剩下位置能排出多少
if k <= p: # 够！就选它
half[i] = ascii_lowercase[j]
break
else: # 不够，跳过整批
k -= p # 平移k
cnt[j] += 1 # 恢复！刚才扣的不算
最后老规矩，镜像合体：
left = ''.join(half)
mid = s[n // 2] if n % 2 else ''
return left + mid + left[::-1]
测试用例全部绿灯。阿整双臂在胸前交叉成一个完美的X，然后缓缓展开，像在空气中画了一个对称的结。
“这个解法，我叫它‘够用就行’。你不需要算清楚每一层能排出多少种，你只需要知道它够不够装下第k个。够了就停——剩下的事，交给截断。”
四、冗余备份
所有测试用例跑完，阿整向后一靠，椅背发出“咔嗒”一声，恰好和他颈椎的舒展声同步。他把整齐宪法放进抽屉，转向我，十指交叉，转向我，显然准备好了总结陈词。
我打了个哈欠。
“其实吧，”我吸着可乐，“你刚才吭哧半天写的两种解法——那个比例递推里的 current_perms * cnt[j] // remaining_length，本质上就是把组合截断里 perm 函数的第一步拆出来单算。同一件事，一个带着状态跑，一个每次都重新乘一遍。数学上完全等价。”
阿整的瞳孔骤缩。他拿起笔，疯狂地在白板上推导。五分钟后，笔掉在地上。这次没滚成圆——直接摔成了两截。
“等价……”他嗓子都劈了，“我折腾了两章……结果是一个解法？！”
“也不能这么说，”我嚼着薯条，“至少你证明了你有两种方式干同一件事。这在强迫症圈子里，叫冗余备份。”
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。