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][0]
    if r &gt; 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?
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[5]+increasing 3479, 5 &gt; 3.
From the increasing tail pick the element just smaller (4), and reverse the tail. 12(4)+decreasing 97[5]3.


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.