This is the 8th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Next permutation

To implement a function that gets the next permutation, the algorithm needs to rearrange a given sequence of numbers into the next larger permutation in the lexicographical order. If no next larger arrangement exists, the numbers are rearranged into the smallest arrangement (that is, in ascending order). Must be modified in place, allowing only extra constant space.

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

One, dictionary order

Before we start, we need to know what a lexicographical order is. Lexicographical order is a size comparison order for any string.

This comparison is not directly related to the length of the string, but rather compares the ASCII values of the characters from left to right. If the characters are the same, continue to compare the next one; If not, the string with the larger character is considered larger (the characters after it are not judged). Here’s an example:

The first three characters are ABC, and the fourth character is different. Obviously, the d of the string ① is greater than the C of the string ②. It is determined that the string ① is greater than the string ②. (The following characters have no effect.)

Second, the problem solving

We are asked to find the smallest sort larger than the given lexicographical order (the next lexicographical order). Therefore, changes to the original lexicographical order should be kept as small as possible.

To do this, we can iterate from right to left to find the first element that appears in descending order (in the traversal direction), such as element 5 in the figure below:

As to why, we can make a simple inference:

If we want to change the last three elements to make the sequence larger, we will find that 764 is already the maximum sequence if we only consider the sequence composed of these three elements; If you change the first element, obviously you get an answer that doesn’t meet the minimum requirement. Therefore, changing the second element 5 is the best solution.

In this way, the elements on the left of the selected element can be ignored, and the right side of the element can no longer be increased. To obtain the smallest larger sequence, element 5 needs to be swapped with the smallest larger element on the right, and the right side should be reversed to obtain the smallest case.

To deal with the general case above, it is also mentioned that if no next larger arrangement exists, the numbers are rearranged into the smallest arrangement (i.e., ascending).

In other words, when the sequence is all descending, the numbers are arranged in ascending order, and a separate processing is done at the end.

Three, code,

func nextPermutation(nums []int)  {
    // Boundary case
   if len(nums) == 1 {
      return
   }

   for i := len(nums) - 1; i > 0; i-- {
      if nums[i] > nums[i- 1] {
         / / switching points
         temp := nums[i- 1]
         for j := len(nums) - 1; j >= i; j-- {
            if nums[j] > nums[i- 1] {
               nums[i- 1] = nums[j]
               nums[j] = temp
               break
            }
         }
         sort.Ints(nums[i:])
         return
      }
   }
   sort.Ints(nums)
   return
}
Copy the code

I’m a little lazy here, and I’m using golang’s sort syntax sugar to reverse the sequence on the right side of the exchange element, but it doesn’t really matter.

Submission result: