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

Question

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 > 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?

Answer 1

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 > 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.