0
\$\begingroup\$

I was practicing python on codewars.com with this question:

Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits. For example:

12 ==> 21

513 ==> 531

2017 ==> 2071

But when I attempted my solution it said it was not optimized enough

Can someone say why it said that?

from itertools import permutations
def next_bigger(n):
    per = list(permutations(str(n)))
    result = []
    for j in per:
        result.append(int("".join(j)))
    for i in sorted(result):
        if i > n:
            return i
\$\endgroup\$
7
  • 6
    \$\begingroup\$ This is more a question for StackOverflow. In any case, you are doing a lot of work, creating all possible permutations, sorting all of them, and then going linearly through the results until you find the right value. You should try to find a smarter algorithm. Have a look at the given examples: what exactly was changed to get the next larger number? Can you reproduce this using the minimum amount of work? Since it's a codewars problem I won't spoil the answer. \$\endgroup\$ – G. Sliepen Sep 25 '20 at 20:40
  • 5
    \$\begingroup\$ @G.Sliepen I'm not certain this belongs on Stack Overflow. The code works. It doesn't have any bugs. It is merely inefficient, which is something which Code Review does focus on. \$\endgroup\$ – AJNeufeld Sep 25 '20 at 22:20
  • 3
    \$\begingroup\$ @AJNeufeld I would normally agree, but this code in particular was written for a coding challenge with performance requirements, and this code doesn't meet those requirements, thus it is not working as intended. \$\endgroup\$ – G. Sliepen Sep 25 '20 at 22:37
  • 2
    \$\begingroup\$ If you turn the numbers into strings, you can look for sub-strings containing larger numbers (assuming the leading digit is unchanged); beware of edge cases (example: 1300 —> 3001). For large numbers (or a sufficient number of numbers), a smart algorithm will be faster than brute-forcing all possible combinations. \$\endgroup\$ – user222150 Sep 26 '20 at 2:29
  • 3
    \$\begingroup\$ The current title of your question is too generic. Please state in title the task accomplished by the code. How do I ask a good question?. \$\endgroup\$ – Marc Sep 26 '20 at 2:44
4
\$\begingroup\$

Time & Memory Complexity

Your code uses a lot of time and memory.

With an \$d\$ digit number, you will get roughly \$d!\$ different permutations of digits. list(permutations(str(n))) will cause all of these permutations to be realized in a list \$d!\$ elements long.

You take this list, and then repeatedly take one permutation from it, convert it into a number, add append it to the end of a result list, growing the list one element at a time. This can be an \$O(k^2)\$ operation, and since \$k\$ in this case is \$d!\$, you have \$O({d!}^2)\$ time complexity.

Next, you take this list, and sort it, which is an \$O(k \log k)\$ operation, or in this case \$O(d! \log {d!})\$.

Finally, you take this sorted list, and loop through it until you find the first value larger than the starting value.

Space complexity: \$O(d!)\$. Time complexity: \$O({d!}^2)\$.

Removing the \$O(k^2)\$

The simplest way to avoid the creation of list, and repeated append operation (which may cause a relocation & copy of all previous elements for each additional element added to it), is to allocate an array of the correct size ahead of time.

Since this is such a common operation, Python even gives us a shortcut: list comprehension. Any code of the form:

destination = []
for value in source:
    destination.append(func(value))

can be rewritten as:

destination = [func(value) for value in source]

The Python interpreter can (via the__length_hint__ from PEP424) tell that it will be allocating a new list of len(container) elements, and may pre-allocate that storage, and then start populating the elements of that list.

(Note: CPython, IronPython, Anaconda, and other big snakes may implement things differently under the hood, possibly amortizing individual appends down to an \$O(1)\$ operation, and may or may not use __length_hint__, but the point still is using list comprehension will always be faster than allocating a list and repeatedly appending elements one at a time.)

We can re-write your function as:

def next_bigger(n):
    per = list(permutations(str(n)))
    result = [int("".join(j)) for j in per]
    for i in sorted(result):
        if i > n:
            return i

Space complexity: \$O(d!)\$. Time complexity: \$O(d! \log {d!})\$.

Removing the \$O(k \log k)\$

Sorting is an expensive operation. We don't want to do it if we don't have to. And we definitely don't have to here; we only want one value as a result.

You are looking for the smallest value, from a list of values, that is larger than the input. We can filter out all values which aren't larger than the input:

    candidates = [value for value in result if value > n]

And then return the minimum of all candidates:

    return min(candidates)

No sorting. Space complexity: \$O(d!)\$. Time complexity: \$O({d!})\$.

Removing the \$O(d!)\$ Space Complexity

There is no reason to store any intermediate results. You could generate your list of permutations, and for each permutation, convert it back to a number, discard any value that isn't larger that the original, and remember the smallest value which passes.

def next_bigger(n):
    per = permutations(str(n))

    result = (int("".join(j)) for j in per)

    candidates = (i for i in result if i > n)

    return min(candidates)

permutations(...) is a generator function, so per is assigned a generator object. We use that generator to construct our own generator that converts a digits of a permutation into an integer, and store that generator in result. We take that generator and create another one which only produces values larger than the original, assigning the generator to candidates.

At this point, no permutations have been created yet. No digits have been joined, and converted to an integer. And no values have been tested for whether they are greater than the original. Only generators for these actions have been created.

Then, we pass the last generator to min(...). The min(...) function asks this generator for a value, and then for another value and save the smaller, and then another value and saves the smaller, and so on. Only the smallest value is preserved at each step.

No list creation. Space complexity: \$O(1)\$. Time complexity: \$O({d!})\$.

Readability

I've used your variable names (n, per, result, j, and i) unmodified in my "improvements". But someone reading the code has to inspect the code to determine that j is a tuple of digits, and i is the corresponding integer value. Better variable names go a long way towards more understandable code. Type hints and """docstrings""" are also extremely useful.

from itertools import permutations

def next_bigger(number: int) -> int:
    """
    For a positive integer, returns the next larger number that can
    be formed by rearranging its digits. For example:

    >>> next_bigger(12)
    21

    >>> next_bigger(513)
    531

    >>> next_bigger(2017)
    2071
    """

    permuted_values = (int("".join(permuted_digits))
                       for permuted_digits in permutations(str(number)))
        
    return min(value for value in permuted_values if value > number)

if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=True)

Of course, for a Code Wars submission, you'd strip out the docstrings, doctest, type hints in the pursuit of speed.

A Better Algorithm

The above are minor improvements on your existing algorithm. As comments and other posts indicate, there is a better algorithm.

\$\endgroup\$
8
  • \$\begingroup\$ Uh... so you're saying you don't know that list.append is amortized O(1)? And I don't believe the list comprehension pre-allocates the space. What makes you think so? \$\endgroup\$ – Kelly Bundy Sep 27 '20 at 11:52
  • \$\begingroup\$ Btw, if you sort n's digits before giving them to permutations, then you can use next instead of min, i.e., stop early. \$\endgroup\$ – Kelly Bundy Sep 27 '20 at 12:03
  • \$\begingroup\$ Oh and it's rather confusing to re-use the name "n" in the complexity analysis for something completely different. \$\endgroup\$ – Kelly Bundy Sep 27 '20 at 12:05
  • \$\begingroup\$ In case it wasn't clear: The repeated appends already are O(n) in total, not just O(n^2) (thus the whole part about removing the O(n^2) is misleading). And as import dis; dis.dis('[int("".join(j)) for j in per]') shows, the list comp doesn't pre-allocate but builds an empty list and then repeatedly does appends as well (at least in CPython), so that part is wrong. \$\endgroup\$ – Kelly Bundy Sep 30 '20 at 17:29
  • \$\begingroup\$ @HeapOverflow Wow, I really messed up my n's, k's, and d's in my complexity analysis. I shouldn't post that late at night. Fixed. Regarding list.append, you'll notice I used "may" in my original wording. As for preallocation, PEP424 officially adds __length_hint__ to the language, so interpreters other than CPython can also do preallocation. Anyhoo, I've added clarification about that to my post, as well. \$\endgroup\$ – AJNeufeld Oct 1 '20 at 22:44
1
\$\begingroup\$

If you think about the numbers and the requirements, you will be able to figure out some properties of numbers that you can use to make your solution more efficient.

Your solution is simple but not efficient, as said in the comments, because for example it creates all the permutations and sorts them. If you have a number 10 digits long, you have a lot of permutations that you create and sort. This is called a "brute force" solution, and is often the easiest to come up with, but far from efficient, for many types of problems.

As an example, if the last digit in the number is larger than the second-last, flipping them will give a larger number that is a good candidate answer without even looking at the other digits. This is one such property that allows you to reduce the search space for potential solutions. Now we may just be looking at 1 candidate, or if we investigate the last 3 digits, we may be looking at about 10 permutations instead of 1000's.

The code you need to write will be larger, because you need to program various special cases. But the run time will be shorter because the program won't have to look at all the permutations, you can exclude most of the numbers without ever trying them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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