Python function to find the next smaller number with same set of digits

Problem: Write a function that takes a positive integer and returns the next smaller positive integer containing the same digits.

My solution:

def next_smaller(n):
import itertools
x = list(str(n)) #list of digits
#permutates and joins digits
x = [int(''.join(i)) for i in list(itertools.permutations(x))]
x.sort() #sorts numerically
#picks number previous to original in list
r = [x[i-1] for i in range(0,len(x)) if x[i] == n]
if r > n: return -1 #returns -1 if no solution
else: return r #returns solution

My code works, however it is terribly inefficient with very large numbers. Any way to make this code more efficient and cut down the execution time?

• – juvian Jul 30 '18 at 20:37

The solution to a good algorithm is a clear logic. Your code uses the "hammers" that are present, spring to mind, and do a tiny bit more than needed. So start to find a logic first.

To get the next smaller number the most strict algorithm would be:

Example: 1253479

• Start from the last digit to the first as long as the digits are decreasing or equal. 12+increasing 3479, 5 > 3.
• From the increasing tail pick the element just smaller (4), and reverse the tail. 12(4)+decreasing 973.

Result: 1249753

The math is relatively simple, and the algorithm linear to the length.

As you see the code can do with the "hammers", functions, you use.

Explanation (on request)

Say you have a number 1253479 = prefix 12, digit 5, and increasing suffix 3479. (5 > 3 hence a smaller permutation on digit+suffix is possible)

An increasing (non-decreasing) suffix 3479 is the first minimum permutation; other permutations like 4379 are greater.

A decreasing (non-increasing) suffix 9753 is the last maximum permutation; other permutations like 9735 are smaller.

Hence a permution++ resp. permutation-- works like:

1 2 5 3 4 7 9
\ / / /
= =
/ \ \ \
1 2 4 9 7 5 3

Roughly reminiscent of increasing/decreasing an integer on paper with a suffix 00...0.

A proof would be more for a math forum.

As this answer has its probably deserved downvotes (it insists on a redesign), I leave it at that.

Following the input from Joop Eggen, I believe the below algorithm works and it is much faster than the original solution in the question. Making a list of all permutations will have an enormously large number of entries for large numbers (like 125658452143250) and will probably stall your computer.

import itertools

def next_smaller(number):
new_number = number
digit = [int(i) for i in str(number)]
digits = len(digit)-1
index_1 = digits-1

while index_1 >= 0:
index_2 = digits
while index_2 > index_1:
if digit[index_2] < digit[index_1]:
digit[index_2], digit[index_1] = digit[index_1], digit[index_2]
_first = digit[0:index_1+1]
_second = digit[index_1+1:]
_second.sort(reverse=True)
digit = _first + _second
new_number  = int(''.join(str(i) for i in digit))
print(f'the next smaller number is: {new_number}')
return new_number

else:
index_2 -= 1

index_1 -= 1

return new_number

def main():
number = int(input('give me a number please: '))
solution=[number]

counter = 0

while counter>-1:
new_number = next_smaller(number)
if new_number < number:
number = new_number
solution.append(number)
counter += 1

else:
print(f'smallest number is found ...\n'
f'number of smaller numbers is {counter}')
break

print(f'solution is \n {solution}')

if __name__ == "__main__":
main()

Thanks to Ruud van der Ham below is a more Pytonic version of the function:

def next_smaller(number):
new_number = number
digit = list(str(number))  # there is no need to convert to numbers. Characters are ok.
digits = len(digit)-1

for index_1 in range(digits-1, -1, -1):  # this is prefered over while
for index_2 in range(digits, index_1-1, -1):  # this is prefered over while
if digit[index_2] < digit[index_1]:
digit[index_2], digit[index_1] = digit[index_1], digit[index_2]
_first = digit[0:index_1+1]
_second = digit[-1:index_1:-1]  # by just backward slicing, there's no need for sort
digit = _first + _second
new_number = int(''.join(digit))
return new_number
return new_number
• This doesn't review the code in the post, on Code Review you are required to make at least one insightful observation to the original code to help the user improve their ability to program, not just the code they're using. – Peilonrayz Aug 8 '18 at 15:38