31_next_permutation.rb

# https://leetcode.com/problems/next-permutation/
#mplement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
#
# If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
#
# The replacement must be in place and use only constant extra memory.
#
#
#
# Example 1:
#
# Input: nums = [1,2,3]
# Output: [1,3,2]
#
# Example 2:
#
# Input: nums = [3,2,1]
# Output: [1,2,3]
#
# Example 3:
#
# Input: nums = [1,1,5]
# Output: [1,5,1]
#
# Example 4:
#
# Input: nums = [1]
# Output: [1]
#
#
#
# Constraints:
#
#     1 <= nums.length <= 100
#     0 <= nums[i] <= 100
# ----------------------------------------------------------------------------------------------------------------------
# @param {Integer[]} nums
# @return {Void} Do not return anything, modify nums in-place instead.
def next_permutation(nums)
  i = nums.length - 2

  i -= 1 while i >= 0 && nums[i + 1] <= nums[i]

  if i >= 0
    j = nums.length - 1

    j -= 1 while j >= 0 && nums[j] <= nums[i]
    nums = swap(nums, i, j)
  end
  nums = reverse(nums, i + 1)
end

def reverse(nums, i)
  j = nums.length - 1
  while i < j do
    nums = swap(nums, i, j)
    i += 1
    j -= 1
  end
  nums
end

def swap(nums, i, j)
  temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
  nums
end