提高itertools.permutations性能

Question

我正在解决的问题是，我创建了一个函数，该函数需要一个正整数并返回可以通过重新排列其数字而形成的下一个更大的数字。例如：12-> 21，513-> 531，12435-> 12453，9817121211-> 9817122111。

我已经在不断提高性能的过程中重新编译了代码，但最终停下来了，我无法更快地获得它。有人有建议吗？它的itertools.permutations行占用了绝大多数时间。

def next_bigger(n):
    num = str(n)
    num1 = set(int(x) for x in str(num))
    if num == num[0] *len(num):
        return -1
    #full_set = set(num)
    lis = set(int(''.join(nums)) for nums in itertools.permutations(num, len(num)))   
    lis = sorted(lis)
    try:
        return int(lis[lis.index(n)+1])
    except Exception:
        return -1

链接到问题：https://www.codewars.com/kata/55983863da40caa2c900004e/train/python

Answer 1

如果您要在“时间复杂度方面”寻求更好的性能，则方法是找到算法的“关键”。在这种情况下，您应该问自己，创建下一个更大的数字意味着什么？答案就像两个相邻数字之间的互换一样简单。代码就是这样。

def next_bigger(n):
num_string = list(str(n))
for i, num in enumerate(num_string):
    if i == len(num_string)-1:
        return -1

    #find two the two numbers one bigger than the other with the minimun order
    if num_string[-i] > num_string[-i-1]:

        aux = num_string[-i]

        #interchange the locations:
        num_string[-i] = num_string[-i-1]
        num_string[-i-1] = aux

        # create a string from the list
        return int("".join(num_string))

您的方法，即使在您提供的链接的测试中花费了相同的时间来完成，在next_bigger(3298463212)之类的情况下也会表现不佳。这是因为您正在执行所有可用的排列，这是一项繁重的计算任务。