+3 votes
by
There is an algorithm for finding the next larger number in permutations of that number. But it is not fast enough.
How can it be improved?

Codeimport itertools

def next_bigger(n):
nlst = list(str(n))

for i in range(len(nlst) - 1, -1, -1):
tempLst1 = nlst[:i]
tempLst2 = nlst[i:]

vs = list(itertools.permutations(tempLst2, len(tempLst2)))

temp = [int("".join(tempLst1 + list(x))) for x in vs if int("".join(tempLst1 + list(x))) > n]
if len(temp) >= 1:
return min(temp)
by
Kit Scribe I have already written an algorithm for this problem in a previous question, it does not require trying all permutations.
by
To rewrite this horror
temp = [int("".join(tempLst1 + list(x))) for x in vs if int("".join(tempLst1 + list(x))) > n]

on a regular cycle

1 Answer

0 votes
by
 
Best answer
I rewrote some of the code into my own shitty code:

spoiler
import itertools
import time
import numpy as np

number = 1020

print("Input number: ",number)

t1 = time.time()
def next_bigger(n):
nlst = list(str(n))

for i in range(len(nlst) - 1, -1, -1):
tempLst1 = nlst[:i]
tempLst2 = nlst[i:]

vs = list(itertools.permutations(tempLst2, len(tempLst2)))

temp = [int("".join(tempLst1 + list(x))) for x in vs if int("".join(tempLst1 + list(x))) > n]
if len(temp) >= 1:
return min(temp)

print("Part 1: %s"%str(next_bigger(number)))


t2 = time.time()


def nb(n):
numlist = np.array(list(str(n)),dtype=int)

i = -1
while i > -len(numlist) and numlist[i-1] >= numlist[i]:
i -= 1
if -len(numlist) == i:
return None

nextnum = i
for j in range(i,0,1):
if numlist[i-1] numlist[j]: nextnum = j numlist[i-1],numlist[nextnum] = numlist[nextnum],numlist[i-1] tail = np.array(numlist[i:]) tail.sort() return ''.join(np.array(numlist[:i],dtype=str)) + ''.join(np. array(tail,dtype=str))print("Part 2: %s"%str(nb(number)))t3 = time.time()print("Time to execute first part of code: %s\nTime to execute second part of code: %s"%(str(t2-t1),str(t3-t2))) Here's the test: $ python3.8 permut.py Input number: 1020Part 1: 1200Part 2: 1200Execution time for the first part of the code: 5.14984130859375e-05The execution time of the second part of the code: 0.00011038780212402344$ python3.8 permut.py Input number: 100000020100000Part 1: 100000021000000Part 2: 1000000210000000000Execution time for first part of code: 0.010196208953857422The execution time of the second part of the code: 0.00019025802612304688 You may notice that on larger numbers, your code gives up position. You can rewrite it using map, but I find it convenient to use numpy.
...