【语法】
一、隐蔽陷阱
求一个排列的字典序下一个:全排列枚举再排序在 n 大时难以实施——从右向左找交换点、反转后段的 O(n) 写法才是正解。
二、底层原理
从右找第一个"小于右邻"的位置 i;再从右找第一个大于它的位置 j,交换两者,随后反转 i 之后的整段。若整串已是降序则已是最大排列,反转整串回绕到最小。231 经交换与反转两步即得 312。
三、正确代码
基础写法(找交换点):
local function swapPivot(t)
local i = #t - 1
while i >= 1 and t[i] >= t[i + 1] do
i = i - 1
end
if i == 0 then return false end
local j = #t
while t[j] <= t[i] do j = j - 1 end
t[i], t[j] = t[j], t[i]
return true
end
进阶写法(完整下一排列):
local function nextPerm(t)
local i = #t - 1
while i >= 1 and t[i] >= t[i + 1] do i = i - 1 end
if i >= 1 then
local j = #t
while t[j] <= t[i] do j = j - 1 end
t[i], t[j] = t[j], t[i]
end
for k = i + 1, math.floor((i + #t) / 2) do
local m = #t + i + 1 - k
t[k], t[m] = t[m], t[k]
end
return t
end
local p = getplayerbyname("perm01")
sendmsg(p, 1, table.concat(nextPerm({2, 3, 1}), ""))
四、引擎验证
231 经交换与反转两步得 312,字典序恰好推进一位;321 已是最大,函数回绕输出 123。
五、FAQ
问:整串降序说明什么?
答:已是最大排列,回绕到最小。
问:复杂度多少?
答:两次线性扫描加反转,O(n)。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【语法】 一、隐蔽陷阱 在字母方阵里找一条上下左右相邻的路径,恰好拼出一个单词且每个格子只用一次:全路径枚举数量爆炸,回溯不…
【游戏】 一、业务场景 秋季活动缺一个轻量竞技,宠物斗武太重、报名太麻烦。斗蛐蛐上线:捕捉野生蛐蛐喂养七日,随后报名斗蛐蛐大…
【语法】 一、隐蔽陷阱 统计 n 枚骰子点数之和的所有组合:递归枚举每枚骰子 6 种点数,6 的 n 次方种组合在 n=10…
【游戏】 一、业务场景 修理铺只修装备耐久,银饰变暗、断裂没人管,玩家只能含泪丢弃。银匠铺上线:银饰进店可选抛光翻新或断口重…
【语法】 一、隐蔽陷阱 从矩阵左上角走到右下角,只能向右或向下,求途经数字之和最小的路线:枚举所有路径有 C(m+n-2, …
【游戏】 一、业务场景 社交玩法除了聊天就是组队,缺一点浪漫仪式。纸鸢寄语上线:写一句 20 字寄语绑上纸鸢放飞,纸鸢随机落…