Next bigger number with the same digits

Question

I have to create a function that takes a positive integer number and returns the next bigger number formed by the same digits: 59853 -> 83559

Please let me know if there are any better solutions. I would like feedback how to improve this.

def next_bigger(num):
    numlist = [int(i) for i in str(num)]

    index_of_replace_num = -1
    i = len(numlist) - 1
    while i > 0:
        if numlist[i] > numlist[i-1]:
            index_of_replace_num = i - 1
            break
        i -= 1

    if index_of_replace_num == -1:
        return -1
    else:
        firstlist = numlist[:index_of_replace_num]
        replaced_num = numlist[index_of_replace_num]
        secondlist = numlist[index_of_replace_num+1:]
        new_replaced_num = 9
        i = 0
        delindex = 0
        while i < len(secondlist):
            if secondlist[i] > replaced_num and secondlist[i] < new_replaced_num:
                new_replaced_num = secondlist[i]
                delindex = i
            i += 1

        secondlist.pop(delindex)
        secondlist.append(replaced_num)
        firstlist.append(new_replaced_num)
        output = firstlist + sorted(secondlist)
        return int(''.join(str(x) for x in output))

Answer 1

Sadly you use an extremely complicated algorithm about which I have not even the slightest clue.

I was lucky enough to follow this link given by @Jaime that suggest a trivially easy algorithm:

1. Find largest index i such that array[i − 1] < array[i].

2. Find largest index j such that j ≥ i and array[j] > array[i − 1].

3. Swap array[j] and array[i − 1].

4. Reverse the suffix starting at array[i].

Converting this into code gives:

def _next_permutation(array):
    i = max(i for i in range(1, len(array)) if array[i - 1] < array[i])
    j = max(j for j in range(i, len(array)) if array[j] > array[i - 1])
    array[j], array[i - 1] = array[i - 1], array[j]
    array[i:] = reversed(array[i:])

Just 4 lines, one for each line in the pseudo-code. This surely is more readable and maintainable than the huge quantity of code you wrote.

Then finishing the problem is just writing a thin wrapper around this that converts numbers to lists of digits and back:

def next_permutation(n):
    array = list(str(n))
    _next_permutation(array)
    return int(''.join(array))

Answer 2

No need to convert to int

Since for all digits '0'...'9', comparison works consistently as you would expect from integers, no need to convert to integers. So instead of this:

numlist = [int(i) for i in str(num)]

You can simplify to:

numlist = list(str(num))

(I would also rename numlist to digits.)

Use range(...)

Instead of manually decrementing loop indexes, for example with i -= 1, it's more idiomatic to use a range(...). For example, instead of:

i = len(numlist) - 1
while i > 0:
    if numlist[i] > numlist[i-1]:
        index_of_replace_num = i - 1
        break
    i -= 1

I recommend this writing style:

for i in range(len(numlist) - 1, 0, -1):
    if numlist[i] > numlist[i-1]:
        index_of_replace_num = i - 1
        break

Use early returns to reduce nesting

Instead of this:

if index_of_replace_num == -1:
    return -1
else:
    # many many lines of code ...

It becomes a bit more readable if you drop the else statement:

if index_of_replace_num == -1:
    return -1

# many many lines of code ...

Decompose to smaller functions

Instead of putting all the logic inside the next_bigger function, it would be good to decompose to smaller logical steps, which can be extracted into their own functions. Decomposing to many smaller functions increases modularity of your programs, makes testing easier, and often leads to reduced duplication.

Alternative implementation

Consider this alternative implementation, with the main method decomposed to smaller logical steps that are unit tested. You can run these doctests with the command:

python -mdoctest next_bigger.py

Empty output means all tests pass (or that there are no tests).

In addition to doctests, it's of course recommended to write proper docstrings too, which I omitted for brevity.

def swap_first_with_higher(digits):
    """
    >>> swap_first_with_higher(list('59853'))
    ['8', '9', '5', '5', '3']

    """
    for pos in range(len(digits) - 1, 0, -1):
        if digits[0] < digits[pos]:
            digits[0], digits[pos] = digits[pos], digits[0]
            break
    return digits


def reversed_tail(digits):
    """
    >>> reversed_tail(list('89553'))
    ['8', '3', '5', '5', '9']

    """
    return [digits[0]] + digits[1:][::-1]


def next_biggest(num):
    """
    >>> next_biggest(59853)
    83559

    >>> next_biggest(111)
    -1

    >>> next_biggest(11211)
    12111

    """
    digits = list(str(num))
    for pos in range(len(digits) - 1, 0, -1):
        if digits[pos-1] < digits[pos]:
            left = digits[:pos-1]
            right = reversed_tail(swap_first_with_higher(digits[pos-1:]))
            return int(''.join(left + right))

    return -1

Answer 3

You seem to be using the proper algorithm, but there are a few things that can be written more compactly. Using the naming in the previous link, I would go with something like:

def next_bigger(num):
    digits = [int(i) for i in str(num)]
    idx = len(digits) - 1
    while idx >= 1 and digits[idx-1] >= digits[idx]:
        idx -= 1
    if idx == 0:
        return -1
    pivot = digits[idx-1]
    swap_idx = len(digits) - 1
    while pivot >= digits[swap_idx]:
        swap_idx -= 1
    digits[swap_idx], digits[idx-1] = digits[idx-1], digits[swap_idx]
    digits[idx:] = digits[:idx-1:-1]
    return int(''.join(str(x) for x in digits))
>>> next_bigger(59853)
83559

YMMV, but compared to your original code, I especially like the compactness of the while loops here, and the use of Pythonic, in-place, list modifying constructs.

Note also that sorting is not necessary, as you have already checked that part of the array is decreasing, you only need to reverse it.

EDIT Corrected the code as suggested by @gardenhead.

Answer 4

I would have attacked this a bit differently than the other answers.

def next_bigger(num) :

Minor nit: I would have used a different name for this. next_permutation perhaps. More important is what's missing, which is the docstring. The docstring is how you document what a function does.

numlist = [int(i) for i in str(num)]

One advantage of this approach over list(str(num)) is that it detects problems early: It raises ValueException on most garbage input. Negative numbers, floating point numbers, strings that that contain non-digits, lists, etc. -- they all bomb. That is a good thing in python.

On the other hand, you'll get a ValueException at the end when you try to convert a goofy string to an integer.

index_of_replace_num = -1
i = len(numlist) - 1
while i > 0:
    if numlist[i] > numlist[i-1]:
        index_of_replace_num = i - 1
        break
    i -= 1
if index_of_replace_num == -1:
    return -1

Minor nit: The name index_of_replace_num is a bit longish. PEP8 says we should keep our lines to less than 80 characters long. Overly long variable names get in the way of that.

Returning a flag value (-1) is not very pythonic. More pythonic would be to raise an exception, or to use an existing search mechanism that raises an exception (and then let it pass). Finally, and most importantly, that's a whole lot of typing.

What we want is the smallest array index p such that the digits after this index are in non-ascending order. This is easy to find. First imagine constructing a list of all of the indices i for which digits[i] < digits[i+1]. This is easy to do with a generator expression: (i for i in range(len(digits)-1) if digits[i] < digits[i+1]). The problem with this is we need the last generated element. That's easy to fix: work in reverse order:

nd = len(digits)
pivot = next(i for i in reversed(range(nd-1)) if digits[i] < digits[i+1])

The above raises a StopIteration exception if there is no such index. The easiest way to deal with that is to simply let that exception pass through up to the caller. Doing the same with your next chunk of code reveals another one-liner:

swap = next(i for i in reversed(range(nd)) if digits[pivot] < digits[i])

Now it's a simple matter of assembling the output. Once again, this is much easier than you made it out to be. Simply swap the values at the pivot and swap points, and then reverse the digits after the pivot point.

Putting this all together yields

def next_permutation(num):
    """ 
    Return the next permutation of the input number.

    The next permutation of a positive integer is the smallest number greater
    than the number in question formed by permuting the number's digits.

    Raises:
    ValueError if the input is a non-empty value that is not a positive integer.
    StopIteration if the input is the empty string or the next permutation
    doesn't exist (e.g., 54321).
    """

    digits = list(str(num))

    nd = len(digits)
    pivot = next(i for i in reversed(range(nd-1)) if digits[i] < digits[i+1])
    swap  = next(i for i in reversed(range(nd)) if digits[pivot] < digits[i])

    digits[pivot], digits[swap] = digits[swap], digits[pivot]
    digits[pivot+1:] = reversed(digits[pivot+1:])

    return int(''.join(d for d in digits))