散文網(wǎng) » 生活 »日常 » 算法解析 Next Permutation 下一個排列

算法解析 Next Permutation 下一個排列

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

實現(xiàn)的功能

它能計算比某一個排列大的所有排列中的最小排列。這里的大小指的是字典序，即把排列看成是? $n$ 進(jìn)制的 $n$ 位數(shù)進(jìn)行比較。如果 $s%3D%5B4%2C3%2C2%2C1%2C5%2C6%5D$ ，將此算法應(yīng)用于? $s$ 將得到? $%5B4%2C3%2C2%2C1%2C5%2C6%5D$ 。

代碼分析

這是 glibc 位于頭文件 bits/stl_algo.h 對函數(shù)?std::next_permutation?的實現(xiàn)，這個函數(shù)能對一個序列應(yīng)用此算法。

這一大段代碼用 OIer 的語氣寫，大概就是這樣。其中?swap?交換兩個變量的值；reverse?反轉(zhuǎn)排列，兩個參數(shù)分別為起點下標(biāo)和終點下標(biāo)加一。

算法分析

從后往前找到第一個（從前往后最后一個）滿足? $a_i%3Ca_%7Bi%2B1%7D$ ?的? $i$ $i$ $a_i$ $。接著向后遍歷?$ $a_i$ ?后比它大的最小的數(shù)? $i%2B1%5Csim%20n$ $a_i$ $i%2B1%5Csim%20n$ ?的數(shù)按從小到大排序就好。因為此時要排序的數(shù)已經(jīng)遞減了，所以能用?reverse?在線性時間內(nèi)完成這里的排序。