31. Next Permutation

I did't know what next permutation really is but I have found some explanations on Wikipedia, and it helped.

Quick Explanation

The explanation below is grab from next permutation section on Wikipedia.

cf. https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

1. Find the largest index k such that a[k] < a[k+1]. If no such index exist, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k+1] up to and including th final element a[n].

Other Resources

• https://www.youtube.com/watch?v=quAS1iydq7U
  • Good resource to understand how it works.

Code

class Solution {
    func nextPermutation(_ nums: inout [Int]) {
        // I have created methods for each step
        let k = findLargestK(&nums) // ①
        if k >= 0 {
            let l = findLargestL(&nums, k) // ②
            swap(&nums, k, l) // ③
        }
        reverse(&nums, k + 1) // ④
    }

    /// Find the largest index k such that a[k] < a[k+1].
    /// If no such index exist, the permutation is the last permutation.
    private func findLargestK(_ nums: inout [Int]) -> Int {
        // We start from the back because we need to find a largest index.
        // -2 for we need an extra space for k+1
        var k = nums.count - 2

        while k >= 0 && nums[k] >= nums[k+1] {
            k -= 1
        }

        return k
    }

    /// Find the largest index l greater than k such that a[k] < a[l].
    private func findLargestL(_ nums: inout [Int], _ k: Int) -> Int {
        // We start from the back because we need to find a largest index.
        var l = nums.count - 1

        while l >= 0 && nums[k] >= nums[l] {
            l -= 1
        }

        return l
    }

    private func swap(_ nums: inout [Int], _ a: Int, _ b: Int) {
        let temp = nums[a]
        nums[a] = nums[b]
        nums[b] = temp
    }

    private func reverse(_ nums: inout [Int], _ start: Int) {
        var lower = start
        var upper = nums.count - 1

        while lower < upper {
            swap(&nums, lower, upper)
            lower += 1
            upper -= 1
        }
    }
}