算法定义
首先看到什么是字典序,就像它的名字一样,是按照字典的顺序(a-z,1-9 ) )。 根据词典顺序,可以求出任意两个字符串的大小。 例如'1' '12 '
以此方式,在已知当前数组的情况下,试图获取下一数组可导致有序集合中的下一个数(正好大于他)。 例如,如果当前数组为" 123456879 ",则正好大于他的下一个数组为" 123456897 "。 当前数组最大时,表示找到了所有数组。
有计算以下数组的算法:
设p为1~n的一个完整序列: p=p1p2. pn=p1p2. pj-1 pjp J1 . PK-1 pkpk1. pn
1 )从排列的右端,找到小于最右边数字的数字j (j从左端计算),即j=max{i|pi
2 )在pj右边的数字中,找到大于pj的数中最小的数字pk,即k=max{i|pipj}全部()右边的数从右向左增加,所以k是大于pj的数中编号最大的
3 )更换pi、pk
4 )再逆转pj1…PK-1pkpk1…pn得到序列p‘=p1p2…pj-1pjpn…PK1pkpk-1…pj1。 这是序列p的下一个序列。
证明
要证明该算法的正确性,只要证明生成的下一个排序是正好大于当前数组的序列即可。 图1.11是从清淡的咖啡豆老师《组合数学》中切取的1234生成所有排序的词典序列树。 从左到右的各根到叶的路径排列成一条。 以这张图为基础,证明上面算法的正确性吧。
算法1,得到的子串s={pj 1,pn}按从大到小的顺序排列。 即,由于j=max{i|pi,所以有pj 1 pj 2 . pn
算法步骤2得到了大于最小pj的pk,n到j的数,大于第一个j的数字。 替换pk和pj以确保替换后的数字大于当前数字。
其中得到的序列为p1p2. pj-1 pkp J1 . PK-1 pjpk-1 . pn。 注意在这里用pk置换了pk。
这个时候,我们注意到了比p1…pj-1PK…,正好比p1…pj…pn大的数字的集合。 我们在这个集合中选择了最小的一个即时要求的下一个数组。
算法的步骤3反转pk后面的数字(从大到小,从小到大)。 )
这样经过上述三个步骤获得的下一个数组正好是大于当前数组的数组。
同时,当发现所有数组时,我注意到数字串按从大到小的顺序排列。 在步骤1中得到的j=0,该算法结束。