|
The easiest way is to present the next permutation in lexicographic order, such as from BECDAFHG to BECDAGFH, except if the highest lexicographic value is presented to it, in which case present the lowest, so that HGFEDCBA produces ABCDEFGH.
To do this, find the last upward transition (F to H in the above example input BECDAFHG), taking the lowest following character that is higher than the found lower end of the transition (in this case finding G, which is higher than F) and using it to replace the latter, and then rearranging the remaining characters, including the displaced one, in lexicographic order. Of course, if there is no upward transition, that is the case in which the subroutine should simply reverse the order of the characters input.
An example with a 4-character string:
abcd last upward trans: cd replace c with d and alphat'z rest
abdc last upward trans: bd replace b with c and alphat'z rest
acbd last upward trans: bd replace b with d and alphat'z rest
acdb last upward trans: cd replace c with d and alphat'z rest
adbc last upward trans: bc replace b with c and alphat'z rest
adcb last upward trans: ad replace a with b and alphat'z rest
bacd last upward trans: cd replace c with d and alphat'z rest
badc last upward trans: ad replace a with c and alphat'z rest
bcad last upward trans: ad replace a with d and alphat'z rest
bcda last upward trans: cd replace c with d and alphat'z rest
bdac last upward trans: ac replace a with c and alphat'z rest
bdca last upward trans: bd replace b with c and alphat'z rest
cabd last upward trans: bd replace b with d and alphat'z rest
cadb last upward trans: ad replace a with b and alphat'z rest
cbad last upward trans: ad replace a with d and alphat'z rest
cbda last upward trans: bd replace b with d and alphat'z rest
cdab last upward trans: ab replace a with b and alphat'z rest
cdba last upward trans: cd replace c with d and alphat'z rest
dabc last upward trans: bc replace b with c and alphat'z rest
dacb last upward trans: ac replace a with b and alphat'z rest
dbac last upward trans: ac replace a with c and alphat'z rest
dbca last upward trans: bc replace b with c and alphat'z rest
dcab last upward trans: ab replace a with b and alphat'z rest
dcba No upward trans; reversing.
abcd
Of course the alphabetizing of the rest mentioned above is simplified by the knowledge that all the rest of the string is already in reverse alphabetic order and the newly displaced letter need only be placed in the re-reversed sequence of those letters.
A subroutine, written in Basic, to do this is:
SUB permute (a$)
DEFINT A-Z
x$ = ""
FOR i = LEN(a$) TO 1 STEP -1
l$ = x$
x$ = MID$(a$, i, 1)
IF x$ < l$ THEN EXIT FOR
NEXT
IF i = 0 THEN
FOR j = 1 TO LEN(a$) \ 2
x$ = MID$(a$, j, 1)
MID$(a$, j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
MID$(a$, LEN(a$) - j + 1, 1) = x$
NEXT
ELSE
FOR j = LEN(a$) TO i + 1 STEP -1
IF MID$(a$, j, 1) > x$ THEN EXIT FOR
NEXT
MID$(a$, i, 1) = MID$(a$, j, 1)
MID$(a$, j, 1) = x$
FOR j = 1 TO (LEN(a$) - i) \ 2
x$ = MID$(a$, i + j, 1)
MID$(a$, i + j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
MID$(a$, LEN(a$) - j + 1, 1) = x$
NEXT
END IF
END SUB
Note that when seeking the smallest following character that exceeds the character being displaced, we are actually looking for the rightmost character that exceeds the character being displaced, as, following this point in the string, the remainder of the characters are in descending sequence, as that was how we defined the character to be displaced.
|
