排列的字典序问题题解

一、原题重述

n 个元素 {1, 2, ..., n} 有 n! 个不同的排列。将这 n! 个排列按字典序排列，并编号为 0, 1, ..., n!-1。每个排列的编号为其字典序值。例如，当 n=3 时，6 个不同排列的字典序值如下：

字典序值	0	1	2	3	4	5
排列	123	132	213	231	312	321

输入格式

第一行是元素个数 n（1 < n <= 8），接下来的 1 行是 n 个元素 {1, 2, ..., n} 的一个排列。题目不会给出最后一个排列。

输出格式

第一行输出计算出的排列的字典序值，第二行输出按字典序排列的下一个排列。

输入样例：

1
2

3
2 3 1

输出样例：

1
2

3
3 1 2

二、引入：P1706 全排列问题

内存限制125.00MB

时间限制1.00s

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入样例：

输出样例：

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

说明/提示

1≤n≤9。

这道题的题意很清晰，即给定一个最大数字 n，求其所有的全排列组合并进行输出。这道题也是相关问题的一个很好的入门情境，我们首先来做一下这道题。

三、算法引入：DFS 与 BFS

1. DFS（Depth First Search）

中文名是深度优先搜索，所谓深度优先，就是说每次都尝试向更深的节点走。

DFS 的核心：一条路先走到底，走不通再回退（回溯）。

在全排列里，可以理解成：

第 1 位先尝试最小可用数字
再去填第 2 位
再去填第 3 位
填满后得到一个完整排列，然后回退到上一步继续尝试

只要每一层都按从小到大的数字尝试，输出天然就是字典序。

2. BFS(Breadth First Search)

中文名是广度优先搜索，所谓广度优先，就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

BFS 的核心：一层一层扩展。

在全排列里可以理解成：

先得到所有“长度为 1 的前缀”
再扩展成所有“长度为 2 的前缀”
再扩展成长度为 3（完整排列）

它更像“按层推进”，通常要额外存储整层状态（队列开销更大）。

说明：在“无权图最短路”场景中，BFS 可以保证先到达的路径边数最少。所以经常被用于寻找最短路的问题。

四、情形模拟

我们以P1706题目的样例为例，给出两种算法各自的一棵搜索树以便于更加直观的理解搜索算法的操作过程

下面两棵树节点结构相同，区别在于“遍历顺序”。

1. DFS 搜索树（深挖 + 回溯）

首先是 DFS，其表述的含义为“每次都尝试向着更深的节点走”。也就是说，如果不抵达某一个终点，它就不会回头；只有彻底完成一次搜索之后，才会回溯来寻找别的情况。

以这道题举例可以理解为：查找从 1 到 n 的全排列，并且要求按照字典序输出。通俗点来说就是从小到大，那我们直接从小到大即从 1 到 n 开始排。以题目中的 3 为例，我们初始手中有 3 个数字：1、2、3，同时要填充三个空位。

第一次填充，我们直接走到终点，即从小到大填充满了 1 2 3。

这里我们已经到达了终点，因此我们要考虑回溯：即撤回到只填充了 1 2 的情况，此时没有别的可能性，那就再撤回到只填充了 1 的情况。此时在第二位我们还有另外一种选择方案，即填充 3，填满后得到一个新的排列： 1 3 2

以此类推，我们可以用搜索树的方式画出 DFS 的过程：

[]
├─ [1]
│  ├─ [1,2]
│  │  └─ [1,2,3]   => 123  (第1个输出)
│  └─ [1,3]
│     └─ [1,3,2]   => 132  (第2个输出)
├─ [2]
│  ├─ [2,1]
│  │  └─ [2,1,3]   => 213  (第3个输出)
│  └─ [2,3]
│     └─ [2,3,1]   => 231  (第4个输出)
└─ [3]
   ├─ [3,1]
   │  └─ [3,1,2]   => 312  (第5个输出)
   └─ [3,2]
      └─ [3,2,1]   => 321  (第6个输出)

DFS 的“过程感”是： [] -> [1] -> [1,2] -> [1,2,3]，然后回退到 [1,2]、[1]，继续尝试 [1,3]...

2. BFS 搜索树（按层扩展）

BFS 的思想与 DFS 不太相同，它是一层一层地展开访问，此时就需要将状态存入内存，寻找所有可能的情况：仍然是 1、2、3 三个可用数字，仍然是三个空位，不一样的是，这次我们要一个位置、一个位置地出发搜索：首先是第一个位置，毫无疑问，1、2、3 三个数字都可以填进去。然后是第二个位置，这时候就要分类讨论了：

对于 1 → 可以填 2 或者 3
对于 2 → 可以填 1 或者 3
对于 3 → 可以填 1 或者 2

（由于我们只讲逻辑不讲具体实现，这里仍然默认为了遵循字典序，所有的尝试都是从小到大进行的）接下来展开第三层位置，此时就要分类讨论一共六种情况…… （此处省略具体分支详细描述）

以此类推，我们可以用搜索树的方式画出 BFS 的过程：

第0层: []

第1层: [1] [2] [3]

第2层: [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]

第3层: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

BFS 的“过程感”是：先把一层全部生成完，再进入下一层。

五、回到原题：四种解法

回到 P1706 全排列问题中，我们可以用如下的一段程序来解决这个问题：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int pd[10], ans[10];
void dfs(int len, int n)
{
    if (len == n)
    {
        for (int i = 0; i < n; i++)
            cout << "    " << ans[i] ;
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!pd[i])
        {
            pd[i] = 1;
            ans[len] = i;
            dfs(len + 1, n);
            pd[i] = 0;
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n ;
    cin >> n;
    dfs(0, n);
    return 0;
}

当然用 BFS 也不是不能做，只不过这道题直接用 DFS 会方便不少；相比之下 BFS 可能还要考虑开二维数组便于进行中间结果的存储。不过手写递归的过程相对来说有些繁琐了，有没有更简单一点的写法呢？

让我们引入两个 C++ 的函数：next_permutation 和 prev_permutation：

next_permutation：用于生成当前序列“下一个”字典序排列的函数。如果当前序列已经是字典序中的最大排列，则返回 false，否则返回 true 并更新原序列为下一个排列。
prev_permutation：与 next_permutation 类似，它是用于生成当前序列“前一个”字典序排列的函数。如果当前序列已经是字典序中的最小排列，则返回 false，否则返回 true 并更新原序列为前一个排列。

卧槽，这不完美贴合这道题的需求吗？直接无敌了！因此这道题的代码可以直接简化成：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n ;
    cin >> n;
    int a[n];
    for (int i = 0; i < n ; i++) a[i] = i + 1;
    for (int i = 0; i < n ; i++)
    {
        cout << "    " << a[i];
    }
    cout << endl;
    while (next_permutation(a , a + n))
    {
        for (int i = 0; i < n ; i++)
        {
            cout << "    " << a[i];
        }
        cout << endl;
    }
    return 0;
}

轻松解决，C++ 太美了。

接下来我们可以回过头来看本篇一开始讲的第一道题（排列的字典序问题）：题目要求我们先判定当前的排列对应的字典序值（从 0 开始），然后输出下一个排列。我们这里给出多种解题角度供参考和学习：

第一种：DFS

刚才我们已经讲过 DFS 是深挖到底再回溯，从小到大逐个生成排列。那么方法很简单：我们让 DFS 直接在现场从小到大生成全体排列，并且每次给一个计数器加一。直到我们发现正在生成的排列和输入的排列完全一样时，输出当前计数器的数目（即它的字典序编号），并且再让 DFS 往前迭代一次（生成下一个排列），输出后截断即可。

第二种：BFS

思路是类似的，但是就这道题来说，在空间上会相对低效一些：先通过 BFS 进行按层次遍历，打表出所有的排列结果；此后从头到尾一一比较并进行标号搜索，当查找到与目标排列一致时停下，再取得下一位进行输出。因为必定需要先把所有的“半成品”都存入队列进而展开，会导致在最后一步搜索前，整个空间里塞满了各种半成品的拼接状态，极度消耗内存。需要注意的是，这并不是说明 BFS 就一定劣于 DFS，只是在这道题的情境上，BFS 不具备优势。在解决“特定状态下最短步数”等问题上，BFS 却有 DFS 无法比拟的优势。

以上两种做法的时间复杂度通常在 $O(n \times n!)$ 量级。

其中：

DFS 的空间复杂度为 $O(n)$。
BFS 的空间复杂度可能会逼近 $O(n \times n!)$（如果不加优化的暴力展开全排列空间）。

第三种：巧妙使用 C++ 内置函数

既然我们都已经知道 C++ 标准库中有可以快速生成排列迭代状态的函数了，干嘛还要自己手写递归搜索？直接上函数就行了：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    int a[n], b[n];
    for (int i = 0; i < n ; i++) 
    {
        cin >> a[i];
        b[i] = a[i];
    }
    // 完成数据输入
    int xv = 0;
    while (prev_permutation(a , a + n))
    {
        xv ++;
    }
    cout << xv << endl;
    // 求字典序
    next_permutation(b , b + n);
    for (int i = 0; i < n ; i++)
    {
        cout << b[i];
        if ( i != n - 1 ) cout << " ";
    }
    // 求下一位排列
    return 0;
}

思路也很清晰：直接根据当前状态分别向前查或向后翻。向前用 prev_permutation 循环查找前面还有多少种排列，这就得到了该序列之前的字典序；向后单次调用 next_permutation 获取下一种排列。

以上这种做法，在最坏情况（例如查找倒数第二个排列）下的时间复杂度为 $O(n \times n!)$，而空间复杂度为 $O(n)$。

以上三种方法的本质思路都非常接近（都是通过生成排列进行匹配），从时间复杂度上也可以有所表现。那么，有没有更优的做法呢？

第四种：阶乘数系统（康托展开）

我们可以用排列组合思想进行纯数学计算。首先给出解题的展开公式：

$$ X = a_n \times (n-1)! + a_{n-1} \times (n-2)! + \dots + a_1 \times 0! $$

1. 为什么会有阶乘 `k!` ？

在一个长度为 $n$ 的排列中，如果我们已经固定了前面的若干位，还剩下 $k$ 个位置没有填。那么这剩下的 $k$ 个数字全排列的种数，正是 $k!$ 种。

阶乘在这里代表了“后缀组合的可能性总数”。

2. 为什么会有系数 `a_i`（即后面有几个比当前数小的数）？

系数 $a_i$ 代表了在当前这一个位置上，我们“跳过”了多少个更小的分支。

我们还是以 **$n=3$**，排列为 2 3 1 为例，模拟一下“从小到大构造排列”的过程，看看我们为了走到 2 3 1，到底“跳过”了多少个更小的排列：

第一位：原本应该填谁？实际填了谁？

我们手上所有可用的数字是 {1, 2, 3}。
当前排列的第一位是 2。
按照字典序，如果第一位填 1，那么无论后面怎么排，整个排列都一定比 2 3 1 小。
如果第一位填 1，后面还有 $2$ 个位置，有 $2!$ 种排法（即 1 2 3 和 1 3 2）。
因为我们第一位直接上了 2，所以我们 跳过了所有以 1 开头的排列 。
跳过的数量 = (比 2 小的可用数字个数) $\times$ (剩下位置的全排列) = $1 \times 2! = 2$ 种。
（这正是公式第一项的物理意义）

第二位：前缀是 2 了，这一位填谁？

我们手上的数字还剩 {1, 3}（2 已经用过了）。
当前排列的第二位是 3。
按照字典序，在第一位都是 2 的前提下，如果第二位填比 3 小的数字（也就是 1），那么生成的排列一定比 2 3 1 小。
如果第二位填 1，后面还有 $1$ 个位置，有 $1!$ 种排法（即 2 1 3）。
因为我们第二位直接上了 3，所以我们 又跳过了以 2 1 开头的排列 。
跳过的数量 = (剩下的数字中比 3 小的个数) $\times$ (剩下位置的全排列) = $1 \times 1! = 1$ 种。
（这正是公式第二项的物理意义）

第三位：最后一位

手上只剩 {1}，当前位也是 1。
没有比 1 更小的可用数字了，所以没有跳过任何分支。
跳过的数量 = $0 \times 0! = 0$ 种。

以上便是判断当前字典序的过程，本质上是借助排列组合的思想进行的拆分。那么，如何求下一位呢？

既然我们能把一个排列“压缩”成一个数字（排名），那么在纯数学的视角下，求下一个排列就变得极其简单：

当前排名 $X \rightarrow$ 下一个排名 $Y = X + 1 \rightarrow$ 将其“解压缩”回排列数组。

在前面的正向计算中，我们是用“比当前数字小的可用数个数”去乘上“阶乘权重”。而在逆向还原时，我们就用目标排名 $Y$ 不断去除以阶乘权重，得到的商和余数就能精准定位每一位该填什么数字。

假设我们有一个存放所有可用数字的池子（从小到大排好序）。

对于第 $i$ 个位置：

除以阶乘求商： 用当前的 $Y$ 除以 **$(n-1-i)!$**。算出来的商 **$q$**，代表着在当前可用的数字池子里， 有 $q$ 个数字比我们要选的数字小 。换言之，我们应该从池子里拿出第 $q + 1$ 小的数字放在这个位置上。
拿走数字： 将选中的数字填入排列，并把它从可用数字池中永久删掉（因为它用过了）。
余数传递： 除法产生的余数 **$r$**，就是剩下的位要继续分配的“排名值”。让 **$Y = r$**，继续去算下一位。

接下来我们以一个与样例不太一样的情形做计算，我们假设要算字典序为5的排列组合应该是多少：

示例演算：以 `Y=5` 为例

初始状态

目标排名：**$Y = 5$**
可用数字池：{1, 2, 3}

第 1 位计算

这一位后面的位置有 2 个，全排列种类（权重）为 **$2! = 2$**。

计算： $5 \div 2 = 2 \dots 1$ （商为 **$2$**，余数为 **$1$**）
商的作用 (选数)： 商是 2，代表在可用的数字里，有 2 个数比我们要选的数小。所以我们去池子 {1, 2, 3} 里找第 3 小的数（索引为 2），也就是 3 。
余数的作用 (传递)： 余数 1 的物理意义是：在第一位确定为 3 之后，对于剩下的位置，我们还需要寻找一个字典序排名为 1 的子排列。
更新： 第一位定为 3，可用数字池变为 {1, 2}。把余数 1 作为新排名传递给下一轮，更新 $Y = 1$。

第 2 位计算

这一位后面的位置有 1 个，全排列种类（权重）为 **$1! = 1$**。

计算： $1 \div 1 = 1 \dots 0$ （商为 **$1$**，余数为 **$0$**）
商的作用 (选数)： 商是 1，代表在剩下的池子里，有 1 个数比我们要选的数小。去池子 {1, 2} 里找第 2 小的数（索引为 1），也就是 2 。
余数的作用 (传递)： 余数变成了 0，这意味着后面的排列不需要再“跳过”任何分支了，剩下的数字直接按从小到大的顺序排即可（即编号为 0 的子排列）。
更新： 第二位定为 2。池子仅剩 {1}。把余数 0 赋值给下一轮，更新 **$Y = 0$**。

第 3 位计算

这一位是最后一位，后面的位置有 0 个，全排列种类（权重）为 **$0! = 1$**。

计算： $0 \div 1 = 0 \dots 0$ （商为 **$0$**，余数为 **$0$**）
商的作用 (选数)： 商是 0。在池子 {1} 中找第 1 小的数（索引为 0），也就是 1 。
更新： 第三位定为 1。池子清空。

总结

最终得到的排列是 3 2 1 。

你能清晰地看到余数的接力过程：

最开始的 $Y = 5$，在第一步除以 $2!$ 时，剥离出了最高位的决策（跳过 2 个大分支）。剩下的余数 1，就变成了后续剩余数字 {1, 2} 组成排列时的新目标排名。

即为：每一次的除法，商用来决定当前位， 余数则完美地将全局排名“等比例缩小”成了局部子排列的排名 ，直到余数归零。

写作代码如下：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n ; i++) 
    {
        cin >> a[i];
    }
    // 完成数据输入
    int fact[n];
    fact[0] = 1;
    for (int i = 1; i <= n ; i++)
    {
        fact[i] = fact[i - 1] * i;
    }
    // 求阶乘，打表
    int xv = 0;
    for (int i = 0; i < n ; i++)
    {
        int cnt = 0;
        for (int j = i + 1; j < n ; j++)
        {
            if (a[j] < a[i]) cnt++;
        }
        xv += cnt * fact[n - 1 - i];
    }
    cout << xv << endl;
    // 正序展开求字典序
    int y = xv + 1;
    bool used[10] = {false};
    int b[n];

    for (int i = 0; i < n; i++)
    {
        int weight = fact[n - 1 - i];
        int q = y / weight;
        y = y % weight;
    
        int count = 0;
        for (int j = 1; j <= n; j++)
        {
            if (!used[j])
            {
                if (count == q)
                {
                    b[i] = j;
                    used[j] = true;
                    break;
                }
                count++;
            }
        }
    }
  
    for (int i = 0; i < n ; i++)
    {
        cout << b[i];
        if ( i != n - 1 ) cout << " ";
    }
    // 逆序展开求下一位排列
    return 0;
}

题解

#算法 #竞赛 #题解

排列的字典序问题题解

https://falling-feather.github.io/2026/04/05/lexicographic-permutation-solution/

作者

Falling_feather

发布于

2026年4月5日

许可协议

排列的字典序问题题解

一、原题重述

输入格式

输出格式

二、引入：P1706 全排列问题

题目描述

输入格式

输出格式

说明/提示

三、算法引入：DFS 与 BFS

1. DFS（Depth First Search）

2. BFS(Breadth First Search)

四、情形模拟

1. DFS 搜索树（深挖 + 回溯）

2. BFS 搜索树（按层扩展）

五、回到原题：四种解法

第一种：DFS

第二种：BFS

第三种：巧妙使用 C++ 内置函数

第四种：阶乘数系统（康托展开）

1. 为什么会有阶乘 k! ？

2. 为什么会有系数 a_i（即后面有几个比当前数小的数）？

示例演算：以 Y=5 为例

初始状态

第 1 位计算

第 2 位计算

第 3 位计算

总结

1. 为什么会有阶乘 `k!` ？

2. 为什么会有系数 `a_i`（即后面有几个比当前数小的数）？

示例演算：以 `Y=5` 为例