字典序排列就是按照字典a-z,1-9的顺序给出字符串的顺序全排列,例如abc的全排列就是从abc一直排到cba。那么给定一个字符串,怎么找出恰好大于该字符串的下一个排列呢?
我们考虑如下的步骤:
1、假设字符串为p1p2….pn,我们从后往前寻找第一个符合pj<pj+1条件的字符pj,也就是说,p1p2…pj-1pjpj+1…pn中pj<pj+1并且pj+1>pj+2>…pn。
2、再次从后往前寻找第一个大于pj的字符pk,也就是说,p1p2pj-1pjpj+1…pk-1pkpk+1…pn中从后往前pk>pj并且pk+1,…pn<pj,可以看出pk也是比pj大的数中最小的一个,因为最差情况下k=j+1。
3、交换pj和pk,这样在p1p2…pj前j个字符变大了,pj放到原来pk的位置上同样符合pj+1>…pk-1>pj>pk+1…>pn。
4、为了得到恰好大于该字符串的下一个排列,我们看到从j+1之后的字符串是降序排列的,我们将其翻转,就可以得到想要的结果了。
那么什么时候整个过程结束呢?当再也找不到符合条件的j时,说明当前的字符串已经是逆序的了,也就是字典序最大。
?
按照这个思路还可以有另一道题目,将abcdef的所有的排列,按照其字典序排列,求其第49个排列 以ab开头的字符串有4*3*2 = 24, 也是字典序中的前24种 以ac开头的字符串有 24种,这是接下来的24种 现在已经到达第48种 所以第49就是adbcef
如果觉得《全排列算法的字典序排列》对你有帮助,请点赞、收藏,并留下你的观点哦!