def swap(nums, i, j):
    temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp

def inplace_sort(nums, begin, end):
    if begin >= end:
        return
    i, j = begin, end
    while i < j:
        swap(nums, i, j)
        i += 1
        j -= 1

class Solution(object):

    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1:
            return
        if nums[n - 2] < nums[n - 1]:
            swap(nums, n - 2, n - 1)
            return
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i < 0:
            nums.sort()
            return
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        swap(nums, i, j)
        inplace_sort(nums, i + 1, n - 1)


if __name__ == "__main__":
    sol = Solution()
    x = [1, 2, 3]
    sol.nextPermutation(x)
    print(x)
    x = [3, 2]
    sol.nextPermutation(x)
    print(x)
    x = [2, 1, 3, 5, 4, 4, 3, 2]
    sol.nextPermutation(x)
    print(x)
