```
class Solution(object):
def nextPermutation(self, nums):
n = len(nums)
if n <= 1: return
# bring the smallest number (greater than the threshold) to the front in the range [start, end] inclusive
def bring_min_to_front(nums, start, end, threshold):
min_index = end
min_value = float('Inf')
found = False
for j in range(end, start - 1, -1):
if threshold < nums[j] < min_value:
found = True
min_value = nums[j]
min_index = j
if found:
nums[start], nums[min_index] = nums[min_index], nums[start]
for i in range(n - 1, 0, -1):
if nums[i - 1] < nums[i]:
"""
1 7 5 2 1
i-1 i
1 2 5 7 1 (bring smallest (2) from [i, n) and > threshold (1) to position i)
i-1 i
2 1 5 7 1 (swap [i-1] and [i])
i-1 i
2 1 1 7 5 (adjust the remaining array from [i, n))
i-1 i
2 1 1 5 7
i-1 i
"""
bring_min_to_front(nums, i, n - 1, nums[i - 1])
nums[i - 1], nums[i] = nums[i], nums[i - 1]
for j in range(i, n): bring_min_to_front(nums, j, n - 1, float('-Inf'))
return
# reverse array if all numbers are in descending order
for i in range(int(n / 2)):
nums[i], nums[n - 1 - i] = nums[n - 1 - i], nums[i]
```