全排列算法的字典序排列

字典序排列就是按照字典a-z,1-9的顺序给出字符串的顺序全排列，例如abc的全排列就是从abc一直排到cba。那么给定一个字符串，怎么找出恰好大于该字符串的下一个排列呢？

我们考虑如下的步骤：

1、假设字符串为p_{1p2….pn,我们从后往前寻找第一个符合pj<pj+1条件的字符pj，也就是说，p1p2…pj-1pjpj+1…pn中pj<pj+1并且pj+1>pj+2>…pn。}

2、再次从后往前寻找第一个大于p_{j的字符pk，也就是说，p1p2pj-1pjpj+1…pk-1pkpk+1…pn中从后往前pk>pj并且pk+1,…pn<pj，可以看出pk也是比pj大的数中最小的一个，因为最差情况下k=j+1。}

3、交换p_{j和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

如果觉得《全排列算法的字典序排列》对你有帮助，请点赞、收藏，并留下你的观点哦！