3
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Peilonrayz Aug 8 '18 at 15:38

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.