Compute next "lexicographical" permutation

next_permutation.py

def next_permutation(nums):
    '''
    brute force:
    - generate all permutations, loop and find the matching, return the next
    - time: O(N^2 * N!) + O(N) [printing/string/char concatenation is the N^2]

    procedure:
    1. find largest increasing suffix
    2. get pivot
    3. find pivot's right-most successor in suffix
    4. swap the pivot and successor
    5. reverse the suffix

    time: O(N)
    space: O(1)

    - GOTCHAS:
    1. not continuing the loop for suffix-1 at 0th index
    2. reverse when the suffix is 0 and exit
    '''
    suffix = len(nums)-1
    while suffix-1 >= 0 and nums[suffix-1] >= nums[suffix]:
        suffix -= 1
    if suffix == 0:
        reverse(nums, 0, len(nums)-1)
        return
    pivot = suffix-1
    successor = len(nums)-1
    for i in range(len(nums)-1, pivot, -1):
        if nums[i] > nums[pivot]:
            successor = i
            break
    nums[pivot], nums[successor] = nums[successor], nums[pivot]
    reverse(nums, suffix, len(nums)-1)
    return nums

def reverse(nums, i, j):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1; j -= 1

import unittest

class TestNextPermutation(unittest.TestCase):
    def test_permutation(self):
        sequence = [0,1,2,5,3,3,0]
        expected = [0,1,3,0,2,3,5]
        self.assertEqual(next_permutation(sequence), expected)

        sequence = [4,8,9,7,5]
        expected = [4,9,5,7,8]
        self.assertEqual(next_permutation(sequence), expected)

        sequence = [1,2,3]
        expected = [1,3,2]
        self.assertEqual(next_permutation(sequence), expected)