# Next Permutation

Sources: leetcode 31

Rating: medium

Given a list nums, re-arrange the numbers into the lexicographically next greater permutation of numbers. If this is not possible, rearrange it as the lowest possible order (sorted in ascending order). Perform the replacement in-place with constant extra memory.

``` def nextPermutation(nums: List[int]) -> None:
# modify nums in-place into next permutation, do not return anything

```

Solution

First, if there are less than 2 values in nums, no change can be made.

``` def nextPermutation(nums):
if len(nums) < 2:
return
# modify nums in-place into next permutation, do not return anything
```

Next, the trick is to realize what the exactly the “next permutation” is and how to find it. To find the next largest permutation, the arrangement occurs at the right most instance of a digit being less than the one immediately right of it. Use an index i starting from the end of nums and iterating left searching for the first instance.

``` def nextPermutation(nums):
if len(nums) < 2:
return
i = len(nums) - 2
while i >= 0 and nums[i+1] <= nums[i]:
i -= 1
# modify nums in-place into next permutation, do not return anything
```

To begin modifying into the next largest permutation, this found value at nums[i] must be swapped with the next largest value to the right of it. Use an index j starting from the end of the list nums and iterating left searching for the next largest value. Once the two indices i and j are found, transforming to the next largest iteration involves swapping the values at nums[i] and nums[j] and then reversing the order of all the digits from i+1 onward.

``` def nextPermutation(nums):
# define swap
# define reverse
if len(nums) < 2:
return
i = len(nums) - 2
while i >= 0 and nums[i+1] <= nums[i]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
swap(nums, i, j)
reverse(nums, i+1)
```

Defining reverse is relatively straightforward. Using two indices i and j starting from opposite ends of the list, swap the values while incrementing i and j until they cross one another.

``` def nextPermutation(nums):
# define swap
def reverse(nums, start):
i, j = start, len(nums) - 1
while i < j:
swap(nums, i, j)
i += 1
j -= 1
if len(nums) < 2:
return
i = len(nums) - 2
while i >= 0 and nums[i+1] <= nums[i]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
swap(nums, i, j)
reverse(nums, i+1)
```

Defining the swap function is a trivial switch in the values between nums[i] and nums[j].

Final Code

``` def nextPermutation(nums):
def swap(nums, i, j):
nums[i], nums[j] = nums[j], nums[i]
def reverse(nums, start):
i, j = start, len(nums) - 1
while i < j:
swap(nums, i, j)
i += 1
j -= 1
if len(nums) < 2:
return
i = len(nums) - 2
while i >= 0 and nums[i+1] <= nums[i]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[j] <= nums[i]:
j -= 1
swap(nums, i, j)
reverse(nums, i+1)
```