labuladong讲解

你好，同学。今天我们来探讨一个全排列问题的有趣变体。在标准的 NOI 搜索专题中，全排列通常要求每个元素“仅能使用一次”。但有时候，竞赛题目会放宽限制，要求我们处理元素可复选（可重复使用）的全排列。

这种题型实际上是** $n$ 进制计数模型**的搜索实现，是理解搜索树“分支限界”概念的最佳入门题。

一、 题目描述 (NOI 风格)

题目名称：可复选全排列 (Permutations with Replacement) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个包含 $n$ 个互不相同整数的序列 $A$。请设计一个算法，找出该序列中元素可以重复挑选的情况下，所有长度为 $n$ 的排列。 例如，输入序列为 {1, 2}，则长度为 2 的可复选全排列为：{1, 1}, {1, 2}, {2, 1}, {2, 2}。

【输入格式】 输入共两行。 第一行包含一个整数 $n$，表示序列中元素的个数，同时也表示目标排列的长度。 第二行包含 $n$ 个以空格隔开的整数，表示序列 $A$ 中的元素。

【输出格式】 输出若干行，每行表示一个符合条件的排列，元素之间用空格隔开。输出顺序按字典序排列。

【样例输入】

3
1 2 3

【样例输出】

1 1 1
1 1 2
1 1 3
1 2 1
... (总计 27 种组合)
3 3 3

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 7$，序列中的元素互不相同且均在 int 范围内。 (注：由于输出量为 $n^n$，当 $n=7$ 时输出行为 823,543 行，已接近 1s 内的 I/O 极限)

二、 预备知识点

1. 深度优先搜索 (DFS)：构造 $n$ 层深的决策树。
2. 乘法原理：每一位都有 $n$ 种选择，总方案数为 $n^n$。
3. 字典序控制：通过对输入数组先进行排序，保证搜索产出的结果天然符合字典序。

三、 启发式思路引导：草稿纸上的推理

请拿出草稿纸，我们对比一下“标准全排列”与“可复选全排列”的差异：

1. 决策分支对比

• 标准全排列：每一层的分支都在减少。第一层选了 1，第二层就只能选 2 或 3。这是因为有 used 数组在“剪枝”。
• 可复选全排列：每一层的分支都是固定的。第一层选了 1，第二层依然可以选 1, 2, 3。

2. 状态空间树

假设 $n=3$，序列为 {1, 2, 3}：

• 根节点（深度 0）：准备填第 1 个位置。
  • 分支：选 1 / 选 2 / 选 3。
• 子节点（深度 1）：填第 2 个位置。
  • 无论父节点选了什么，当前节点依然有三个分支：选 1 / 选 2 / 选 3。
• 结论：这棵树是一棵高度为 $n$ 的满 $n$ 叉树。

3. 为什么“放飞自我”？

正如你所观察到的，标准算法中的 used[i] 是为了限制重复。如果允许重复，我们只需要把“检查 used 标记”和“设置/还原 used 标记”的逻辑全部删掉，让递归函数在每一层都从 0 循环到 n-1 即可。

四、 复杂度分析与建议

• 时间复杂度：$O(n \cdot n^n)$。
  • 总共有 $n^n$ 个叶子节点。
  • 每个排列的输出需要 $O(n)$。
• 空间复杂度：$O(n)$。
  • 递归深度为 $n$，仅需一个长度为 $n$ 的 path 数组。
• 优化建议： 由于输出量巨大（$7^7$ 超过 80 万行），在 NOI 竞赛中必须使用 "\n" 替代 endl，且建议使用 printf 或 fast I/O。

五、 算法流程图 (C++14 伪代码)

我们通过流程图展示这种“无约束”的搜索逻辑：

graph TD
    Start(开始) --> SortAction("对输入序列 nums 排序保证字典序")
    SortAction --> Init("初始化 path 数组, 深度 d = 0")
    Init --> CallDFS("调用 DFS-d")

    subgraph DFS_Function [递归搜索函数]
    CheckDepth{d 等于 n ?}
    CheckDepth -- Yes --> Output("输出当前 path 序列并返回")
    CheckDepth -- No --> LoopInit("循环 i 从 0 到 n-1")
    
    LoopInit --> Action("path-d 等于 nums-i")
    Action --> Recur("递归调用 DFS-d+1")
    Recur --> NextI("i 增加 1")
    NextI --> LoopInit
    end

    Output --> Return((返回上一层))
    LoopInit -->|循环结束| Return

六、 读题关键词总结

在 NOI 读题时，如何识别“可复选全排列”？

1. “元素可以重复使用/选取” (Elements can be reused)：核心标志。
2. “所有可能的长度为 $n$ 的序列”：说明是排列模型。
3. “互不相同”与“可复选”同时出现：意味着你可以把输入数组看作是一个 $n$ 进制数的每一位可选的符号集。
4. 注意 $n$ 的范围：如果 $n$ 只有 7-8，大概率是这种 $n^n$ 的搜索；如果 $n$ 很大（如 100），可能是动态规划。

教练寄语： 同学，可复选全排列是搜索中最纯粹的形式。它没有任何约束（Pruning），每一层都是完整的。理解了它，你就理解了搜索空间的“广度”是如何爆炸的。记住，DFS 只是工具，理解决策树的结构才是竞赛的灵魂。加油！