31. Next Permutation

Stanislav Gumeniuk included in Leetcode Leetcode-Problem

2020-04-10 320 words 2 minutes

Contents

Automatic Translation

This article has been translated automatically from Russian to English. The original is available in Russian.

Solution to problem 31 “Next Permutation” from LeetCode.

Problem Statement

You need to implement next permutation, which will sort the number in lexicographic order for the next permutation of numbers. If such a permutation is impossible - you need to sort the numbers in ascending order.

Note

The permutation must be performed inside the array and use constant memory

Example

    1,2,3 → 1,3,2
    3,2,1 → 1,2,3
    1,1,5 → 1,5,1

Solution

Find the Permutation

The idea is…

Go from the end of the array. Take the current element and go to the beginning, along a non-decreasing sequence. As soon as you encounter an element breaking the non-decreasing sequence - remember its index.
Then go right from this element in search of an element that is greater than the current one by the minimum value. When found - swap these two elements. And sort all elements to the right of the current one in ascending order.
Optional, if nothing was found in the first point - sort the array in ascending order

func nextPermutation(nums []int)  {
    ordered := false
    pos := len(nums)-1
    for idx := len(nums)-1; idx>=0; idx--{
        if ordered {
            continue
        }
        for jdx := idx; jdx>0; jdx -- {
            if !ordered && nums[jdx-1]<nums[jdx]{
                ordered = true
                pos = jdx-1
            }
        }
    }


    if ordered {
        maxdist := math.MaxInt32
        maxpos := pos
        for idx:= pos+1; idx<len(nums);idx++ {
            if nums[idx]>nums[pos] && nums[idx]-nums[pos]<maxdist {
                maxdist =  nums[idx]-nums[pos]
                maxpos = idx
            }

        }

        nums[maxpos], nums[pos] = nums[pos], nums[maxpos]

        pos++
        for idx:= pos; idx<len(nums);idx++ {
            k := idx
            for jdx := idx;jdx>=pos;jdx-- {
                if nums[k]<nums[jdx]{
                        nums[k], nums[jdx] = nums[jdx], nums[k]
                        k=jdx
                }
            }
        }
    }


    if !ordered {
        for idx := len(nums)-1; idx>=0; idx--{
            for jdx := idx; jdx>=0; jdx -- {
                if nums[idx]<nums[jdx]{
                    nums[idx], nums[jdx] = nums[jdx], nums[idx]
                    ordered = true
                }
            }
    }
    }
}