按字典序算法全排列

梦里梦外; 2021-09-14 02:40 442阅读 0赞

## **一、简介** ##

[原文][Link 1]

按照字典里的排序方法：
    先比较第一个字符
    i 和 b
    b<i b是第2个 ，i是第9个 2 < 9
    于是 baray < ilove
    如果第一位相同，就比较第二位，
    例如：
    abcdd<abcde
    aaaay<aaaaz
    如果其中之一是另一个的前缀，则短的那个排前面：
    aaa < aaab

[来自百度百科][Link 2]

算法如下：
    设P是数字1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn
    1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi<pi+1}。如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。
    2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）。
    3）对换pj，pk。
    4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。

例如：  
对于2763541找出字典序的下一个排列。  
2763541 （从右至左首先出现的是35，3<5）；  
2763541 （在3的位置之后从右至左找到第一个比3大的数4）；  
2764531 （交换3,4的位置）；  
2764135 （把原来3的位置现在4位置后面的数值5,3,1反转）。

解：就是找到比2763541大的但是同时在1、2、3、4、5、6、7所有排列中比2763541大的程度中最小的一个。为了找到大的程度最小的，一般保证前面的数字位置不调换，优先调换后面数字的排列。首先注意到541是按照降序排列（为什么是降序，只要按照字典序算法，后面就一直这样。），如果我们想通过调换541的位置显然不行,5>4>1，当我们遇到3时，发现有戏，因为在3的后面有比3大的数字，我们把3往后调，把一个大的数字往前调就能把排列整体变大。那么3后面有5和4，我们选择哪一个的，显然是4，因为其增大程度较小。有因为3<4，所以调换位置后后面数字依然是降序，我们只要将其调成升序即可变成最小。

[例题LeeCode : 31. Next Permutation][LeeCode _ 31. Next Permutation]

[Link 1]: https://zhidao.baidu.com/question/83236318.html
[Link 2]: https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F/7786229?fr=aladdin
[LeeCode _ 31. Next Permutation]: https://blog.csdn.net/qq_16234613/article/details/89920198