Как можно улучшить алгоритм, чтобы он быстрее работал?

Question

[Kit Scribe]

Есть алгоритм по поиску следующего большего числа в пермутациях этого числа. Но он недостаточно быстрый.
Как можно его улучшить?

Код

import 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)

Comments

[javedimka]

Переписать вот этот ужас
temp = [int("".join(tempLst1 + list(x))) for x in vs if int("".join(tempLst1 + list(x))) > n]

на обычный цикл

[o5a]

Kit Scribe, я в предыдущем вопросе по этой задаче уже написал алгоритм, она не требует перебора всех перестановок.

Answer 1

[Ищю в поисковиках]

Переписал часть кода на свой говнокод:

spoiler

import itertools
import time
import numpy as np

number = 1020

print("Входное число: ",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("Часть 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] and numlist[nextnum] > 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("Часть 2: %s"%str(nb(number)))


t3 = time.time()

print("Время выполнения первой части кода: %s\nВремя выполнения второй части кода: %s"%(str(t2-t1),str(t3-t2)))

Вот тест:

$ python3.8 permut.py 
Входное число:  1020
Часть 1: 1200
Часть 2: 1200
Время выполнения первой части кода: 5.14984130859375e-05
Время выполнения второй части кода: 0.00011038780212402344

$ python3.8 permut.py 
Входное число:  100000020100000
Часть 1: 100000021000000
Часть 2: 100000021000000
Время выполнения первой части кода: 0.010196208953857422
Время выполнения второй части кода: 0.00019025802612304688

Можно заметить, что на больших числах, ваш код сдает позиции.

Можно преобразования переписать через использование map, но мне удобно numpy использовать.

Comments

[Kit Scribe]

Моя версия

def next_bigger(n):
    n_lst = list(map(lambda x: int(x), str(n)))

    for i in range(len(n_lst) - 1, 0, -1):
        if n_lst[i] > n_lst[i - 1]:
            left_side = n_lst[:i]
            right_side = n_lst[i:]
            right_side.sort()

            for i2 in range(len(right_side)):
                if right_side[i2] > left_side[-1]:
                    temp = left_side[-1]
                    left_side[-1] = right_side[i2]
                    right_side[i2] = temp
                    return int("".join(str(x) for x in left_side + right_side))

    return -1

P.S. Я полагаю, только raw python можно использовать