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.
