我的算法书 - 类循环排列

一句话算法

类循环排列就是把不确定层数的 for 循环，改写成一层一层填写位置的 DFS。

问题模型

给定两个整数 n, m，有 n 个位置，每个位置都可以放一个 $[0,m-1]$ 中的数。

要求按字典序输出所有可能序列。

例如：

n = 3, m = 2

所有序列是：

如果 n=3 固定，可以写三层循环：

cpp

        1
2
3
4

        for (int a = 0; a < m; ++a)
  for (int b = 0; b < m; ++b)
    for (int c = 0; c < m; ++c)
      cout << a << ' ' << b << ' ' << c << '\n';

但当 n 是输入时，循环层数不能提前写死，这就需要递归。

核心直觉

把“第几层循环”看成 DFS 的参数。

dfs(1): 填第 1 个位置
dfs(2): 填第 2 个位置
...
dfs(n): 填第 n 个位置
dfs(n+1): 输出完整序列

每一层都枚举：

0, 1, 2, ..., m-1

只要每层都按从小到大的顺序枚举，最终输出自然就是字典序。

算法步骤

用 path[1..n] 保存当前序列。
定义 dfs(dep)，表示正在填写第 dep 个位置。
如果 dep > n，说明所有位置都填完，输出 path。
否则枚举 x = 0..m-1：
- 令 path[dep] = x。
- 递归 dfs(dep + 1)。

算法证明

关键不变量：进入 dfs(dep) 时，path[1..dep-1] 已经是某个合法前缀。

初始 dfs(1) 时，空前缀合法。
在 dfs(dep) 中，当前位置枚举了所有 $0..m-1$ 的取值，因此每个合法前缀都会扩展出全部可能下一位。
当 dep > n 时，前缀长度正好为 n，得到一个完整序列。
任意完整序列都由它的第 1 位、第 2 位、…、第 n 位唯一决定，因此只会走到一条 DFS 路径，不会重复。

所以算法不重不漏地输出所有长度为 n 的 $m$ 进制序列。

字典序也成立：在同一个前缀下，当前位置按 0..m-1 递增枚举；更靠前的位置先被固定，所以整体输出顺序就是字典序。

复杂度分析

一共有：

m^n

个序列，每个序列输出 n 个数。

时间复杂度： $O(n\cdot m^n)$ 。
空间复杂度： $O(n)$ ，用于递归栈和 path。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

        #include <bits/stdc++.h>
using namespace std;

// 递归实现 n 层循环，每层都从 [0, m) 中选择一个值。
// emit(path) 会收到一个长度为 n 的完整序列。
template <class Emit>
void enumerate_dynamic_loop(int n, int m, const Emit& emit) {
    if (n < 0 || m < 0) return;

    vector<int> path(n, 0);

    auto dfs = [&](auto&& self, int dep) -> void {
        if (dep == n) {
            emit(path);
            return;
        }

        for (int x = 0; x < m; ++x) {
            path[dep] = x;
            self(self, dep + 1);
        }
    };

    dfs(dfs, 0);
}

测试用例

输入：

3 2

输出：

输入：

2 3

输出：

应用分类详解

类循环排列的本质是“每个位置独立选择一个值”。它是全排列、组合、子集枚举等回溯算法的基础模型。

一、固定长度序列枚举

典型模式： 长度固定，每个位置都有相同取值范围。

识别信号： 输出所有长度为 n 的串、每位取 0..m-1、循环层数由输入决定。

核心建模： dep 表示当前位置，path 保存当前前缀。

应用场景	经典题目	核心思路
01 序列	本书 01 序列枚举	令 `m=2`
m 进制序列	所有状态暴力	每层枚举 `0..m-1`
密码枚举	固定字符集暴力	每位选择一个字符

二、回溯搜索入门

典型模式： 每一步做一个选择，最后得到一个完整方案。

识别信号： 所有方案、DFS、回溯、搜索树。

核心建模： 每个递归节点是一段前缀，每条边是追加一个新选择。

三、状态空间暴力

典型模式： 需要枚举所有状态再检查条件。

识别信号： 数据范围很小， $m^n$ 可以接受。

核心建模： 先生成所有候选序列，再用题目条件过滤或计算答案。

经典例题

1. 输出所有 01 串

把 m 固定为 2，就是长度为 n 的 01 序列枚举。

2. 输出所有 m 进制数

长度为 n，每位取 0..m-1，本篇模板可以直接使用。

3. 全排列的前置模型

全排列也是一层一层填位置，只是需要额外限制“同一个元素不能重复使用”。因此在这个模板上加 used 数组，就得到全排列 DFS。

参考

本书递归实现多重循环章节：recursion/dynamic_loop/index.md
本书 01 序列枚举章节：enumeration_permutaion_combination/01_sequence/index.md
本书全排列章节：enumeration_permutaion_combination/permutation/full_permutation/index.md