11
\$\begingroup\$

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))
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Jan 2, 2016 at 11:48
  • \$\begingroup\$ Thanks for accepting my answer. For the record, there are some better new answers now, feel free to accept the best one, no hard feelings! \$\endgroup\$
    – janos
    Jan 2, 2016 at 22:18
  • \$\begingroup\$ @janos Thanks, your answer was very detailed, and it helps me to learn Python. I am a newbie in software development. \$\endgroup\$
    – mrakosms
    Jan 3, 2016 at 0:40

4 Answers 4

5
\$\begingroup\$

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))
\$\endgroup\$
2
  • \$\begingroup\$ That's very similar to what I wrote, except I used next rather than max. \$\endgroup\$ Jan 2, 2016 at 22:11
  • \$\begingroup\$ @DavidHammen yup, given a problem there are just a few good solutions, that most often look similar. Great minds think alike :P \$\endgroup\$
    – Caridorc
    Jan 2, 2016 at 22:12
5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I believe that should be idx >= 1 in line 4. Also, mightdigits[idx:] = reversed(digits[idx:]) be cleaner? (I am not a Python style expert). \$\endgroup\$
    – gardenhead
    Jan 2, 2016 at 6:10
  • \$\begingroup\$ Thanks, but in line 10 is IndexError. \$\endgroup\$
    – mrakosms
    Jan 2, 2016 at 10:30
  • \$\begingroup\$ @gardenhead Yes, you are absolutely right. That little change also takes care of @mrakosms IndexError. As for the reversing, I like slice syntax a lot, and would prefer something like digits[idx:][::-1], although your proposal is perfectly fine. \$\endgroup\$
    – Jaime
    Jan 2, 2016 at 14:21
3
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.