回溯生成：从空排列长出选择树

下一个排列是「一个接一个」地走；回溯 (backtracking) 换一个视角看同一批排列：从空排列开始，逐位选一个还没用过的数填进去，填满即得一个排列；一个分支试完就撤销去试别的。把所有选择画出来，就是一棵选择树——根是空，每向下一层固定一位，每片叶子恰好是一个完整排列。$n$ 个元素两两互异时共 $n!$ 片叶子。

1 · 一步选择的三个动作

在某一位选定一个数后，把它标记为已用并递归去填下一位；当这条路探到底或试完回来时，必须撤销刚才的选择——把数从部分排列里弹出、重新标记为可用——才能公平地尝试同一位上的其他候选。撤销这一步就是 backtracking 这个名字的来历。

实测规模与 $n!$ 对得上：$n = 3$ 是 6 片叶子、16 个节点、32 帧；$n = 4$ 是 24 片叶子、65 个节点、130 帧；$n = 5$ 是 120 片叶子、326 个节点、652 帧。

2 · 叶子的顺序

只要每一位都按与比较序相同的顺序遍历候选（实现里是 for (let v = 1; v <= n; v++) 加 used 过滤），深度优先到达叶子的先后就与反复调用 next 得到的字典序完全一致。$n = 3$ 与 $n = 4$ 下两条序列逐项相等。元素不是 $1 \dots n$ 时，需要先把候选排好序，这个一致性才成立。

3 · 参考文献

1. Knuth, D. E. (2011). The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. §7.2.1.2.