算法解析 Next Permutation 下一个排列

2023-02-18 19:58 作者:EKVTGwNJiElK 0人读过 | 我要投稿

实现的功能

它能计算比某一个排列大的所有排列中的最小排列。这里的大小指的是字典序，即把排列看成是 $n$ 进制的 $n$ 位数进行比较。如果 $s%3D%5B4%2C3%2C2%2C1%2C5%2C6%5D$ ，将此算法应用于 $s$ 将得到 $%5B4%2C3%2C2%2C1%2C5%2C6%5D$ 。

代码分析

这是 glibc 位于头文件 bits/stl_algo.h 对函数 std::next_permutation 的实现，这个函数能对一个序列应用此算法。

这一大段代码用 OIer 的语气写，大概就是这样。其中 swap 交换两个变量的值；reverse 反转排列，两个参数分别为起点下标和终点下标加一。

算法分析

从后往前找到第一个（从前往后最后一个）满足 $a_i%3Ca_%7Bi%2B1%7D$ 的 $i$ $i$ $a_i$ $。接着向后遍历$ $a_i$ 后比它大的最小的数 $i%2B1%5Csim%20n$ $a_i$ $i%2B1%5Csim%20n$ 的数按从小到大排序就好。因为此时要排序的数已经递减了，所以能用 reverse 在线性时间内完成这里的排序。