Next Permutation

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums