Next Bigger Number when given an int

Question

I'm having trouble optimizing my algorithm for finding the next biggest number with the same digits when given an integer, returning -1 if there is no bigger number.

Examples of what the function should do:

next_bigger(13): ---> 31

next_bigger(201): ---> 210

next_bigger(2017): ----> 2071

next_bigger(10) -----> -1

next_bigger(587) -----> 758

I thought using itertools.permutations() would be my best bet for the problem, but the time complexity is demanding.

Here's my code so far:

import itertools

def next_bigger(n):
    x = list(itertools.permutations(str(n), len(str(n))))
    lst = [int(''.join(x[i])) for i in range(0, len(x))]
    lst.sort(reverse=True)
    if n == lst[0]:
        return -1
    for i in range(0, len(lst)):
        if lst[i + 1] == n:
            return lst[i]

I tried wrapping the list in a set and then back into a list to remove duplicates but that didn't help. I also tried an if statement in the list comprehension where the list would only include values greater than the original number 'n'.

Answer 1

The other answers explain what the approach is. I just reiterate the steps to have a complete answer:

1. Starting from the right, find the first digit that is less than its successor. If there is none, there is no greater number possible.

2. Consider the section at the right of that found position. We know the digits in that section are sorted in non-increasing order (because of the previous step). From that section, choose the digit that is the least among those that are greater than the digit found in step 1.

3. Swap the two found digits. This means that the section of step 2 is still sorted in non-increasing order. Then reverse that section. The swap and reversal can be done in one expression.

I provide here an implementation that stops the explicit iteration when the digit to augment has been identified (step 1), and reconstructs the resulting string by piecing the pieces (reversed) together, using string slicing:

def next_bigger(n):
    s = str(n)
    for i in range(len(s) - 2, -1, -1):
        if s[i] < s[i + 1]:
            for k in range(len(s) - 1, i, -1):
                if s[i] < s[k]:
                    return int(s[:i] + s[k] + s[-1:k:-1] + s[i] + s[k-1:i:-1])
    return -1