leetcode: 31. Next Permutation

# coding=utf-8
# 假设数组中所有数值组成的排列组合是个循环列表，则返回该输入组合的下一组合。
#
# Implement next permutation, which rearranges numbers 
# into the lexicographically next greater permutation of numbers.
#
# If such arrangement is not possible, 
# it must rearrange it as the lowest possible order (ie, sorted in ascending order).
#
# The replacement must be in-place, do not allocate extra memory.
#
# Here are some examples. 
# Inputs are in the left-hand column 
# and its corresponding outputs are in the right-hand column.
# 1,2,3 -> 1,3,2
# 3,2,1 -> 1,2,3
# 1,1,5 -> 1,5,1

假设数组中所有数值组成的排列组合是个循环列表，则返回该输入组合的下一组合。

nums[k:]的盈满则亏之演。

class Solution():
    def nextPermutation(self, x):
        pre, later = -1, 0
        for i in range(len(x) - 1):
            if x[i] < x[i + 1]:
                pre = i    # [pre+1:len(x)]为全数组中最后一个降序。
        if pre == -1:
            x.reverse()    # 全程降序，那还找个毛，直接回到循环列表表首咯 （。・・）ノ
            return
        for i in range(pre + 1, len(x)):
            if x[i] > x[pre]:
                later = i    # 因为k之后必定是降序的，所以最后跑出来的l必定是k之后 比 x[pre] 大的最小元素 的下标。
        x[pre], x[later] = x[later], x[pre]
        x[pre + 1:] = x[:pre:-1]    # 每次对于 x[pre:] 来说，都是一次overflow，所以一定是从最满（降序）变成最底（升序）


if __name__ == "__main__":
    nums = [1, 4, 3, 2]
    Solution().nextPermutation(nums)
    assert nums == [2, 1, 3, 4]