Current permutation should share longest prefix with next permutation and it's very similar to a
carry in addition. Three steps: 1) from right to left find the longest increasing sequence, 2)
carry to the previous number, 3) reverse the increasing sequence.
def nextPermutation(self, nums): # from right to left find longest increasing sequence i = len(nums) - 1 while i > 0 and nums[i - 1] >= nums[i]: i -= 1 # swap nums[i - 1] and min(number in nums[i...end] which is larger than nums[i - 1]) # consider it as a carry to nums[i - 1] if i > 0: j, pre = len(nums) - 1, nums[i - 1] while j >= i and nums[j] <= pre: j -= 1 nums[i - 1], nums[j] = nums[j], nums[i - 1] # reverse nums[i...end] k = len(nums) - 1 while i < k: nums[i], nums[k] = nums[k], nums[i] i, k = i + 1, k - 1