# Next permutation challenge

**Problem statement**

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.

**Sample input 1**

1 |
[1,2,3] |

**Sample output 1**

1 |
[1,3,2] |

**Sample input 2**

1 |
[3,2,1] |

**Sample output 2**

1 |
[1,2,3] |

**Solution**

We will iterate over the array backwards, starting from the end and search for the first element that we can swap with a preceding element. The condition is, that the preceding element must be smaller than the current element. In other words, we want to increase the number that resides at the index, of the preceding element by swapping. For instance, if the input were to be we would start with the trailing and try to find a preceding element that is smaller. For we don’t have such an element. We then continue with at index and find that we can swap it with the at index . We note down both indices (indices and ) and continue. Next, we search a preceding element for the element at index . We find that is greater than the element at index and compare those indices with and . We can see that from the previous iteration we noted down index and now we have found a larger index, . For our purpose is better than because it still results in a larger permutation when we swap, but still smaller than when we would swap index . That is why we update our and to and . We continue our backwards iteration until we surpass .

Finally, we just have to sort the part of the array starting at index in ascending order.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
class Solution(object): def nextPermutation(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ print(nums, end='', flush=True) r = len(nums) - 1 i = -1 max_index = -1 cursor_index = -1 while True and r >= max_index: cursor = r i = cursor - 1 while i >= 0 and nums[cursor] <= nums[i]: i -= 1 if i >= 0: if i > max_index: max_index = i cursor_index = cursor r -= 1 if cursor_index >= 0: tmp = nums[cursor_index] nums[cursor_index] = nums[max_index] nums[max_index] = tmp result = nums[:max_index+1] + sorted(nums[max_index+1:]) for i in range(0, len(result)): nums[i] = result[i] else: nums.sort() def main(): solution = Solution() solution.nextPermutation([1, 2, 3]) solution.nextPermutation([1, 2, 0]) solution.nextPermutation([2, 4, 1, 3, 2]) solution.nextPermutation([1, 1, 5]) solution.nextPermutation([1]) solution.nextPermutation([]) solution.nextPermutation([3, 2, 1]) solution.nextPermutation([1, 3, 2]) solution.nextPermutation([1,5,1]) solution.nextPermutation([4,2,0,2,3,2,0]) if __name__ == "__main__": main() |