Why the algorithm use longest suffix, swap and reverse


  • 0
    C

    Consider 1,2,3,4 , what is next permutation(ie, with higher weight)?
    1,2,4,3 , Why?
    Because by only changing the right digits, we can avoid changing left digits that have higher weight so that weight won’t increase too much.
    What is next permutation?
    1,2,?? Not enough! Because we can not find a way moving just right two digits to acquire a higher weight permutation. So we need to modify right three digits at least or say suffix needs to be longer.
    Pause, Why can’t we just modigy the right two digits any more?
    We can discover that in original permutation 1,2,3,4 , all digits values are in ascending order which means left digits have lower values than right digits. But as for subsequent permutation, we put larger value right of smaller value, like 4 in right of 3 or D in right of C, in order to get a higher weight. When we can not increase the weight only by putting large value right of small value, we need to modify the order of one more right digits, just like when you add 1 to 99, you need one more digit to carry 1 in 100.
    So we confirm that if the suffix is in descending order(have been used up), we need to extend suffix with one more digit. In order words, suffix should be the longest descending sequence counting from right.
    Who take the place of digit 2?
    It should be 1,3,?? Why?
    Next permutation corresponds to a larger weight but the least weight increment. We replace 2 with 3, becase we should find the next larger value than the largest value in prefix to statisfy the least weight increment condition. Where is the largest value?
    Observing that original permutation is in ascending order and foregoing operations only modify the suffix, the prefix session is still in ascending order which means the rightmost digit is the largest value in prefix.
    Therefore after we identify the suffix as well as prefix, we replace rightmost digit of prefix with the next larger digit in suffix. Because the suffix has already been in descending order, if counting from right to left, the first digit larger than “2” we met should be desirable.
    Then, 1,3,?? => 1,3,2,4 , Why?
    New suffix should be in ascending order. Note that just now before replacement, the suffix is in descending order. Can we insert “2” into previous position of digit 3 and then reverse whole suffix directly? Yes
    Because suffix is in descending order and “2” should fall between digit 3 and digit right of 3.
    We can swap rightmost digit in prefix with first larger right digit in suffix, and then reverse whole suffix.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.