使排列函数更有效

Question

我正在解决一个代码战争卡塔问题，但正在努力弄清楚如何使我的函数更高效，因为我一直被涉及大量数字的测试用例所困扰。

卡塔的说明如下：

创建一个函数，它接受一个正整数并返回可以通过重新排列其数字形成的下一个更大的数字。例如：

12 ==> 21
513 ==> 531
2017 ==> 2071
nextBigger(num: 12)   // returns 21
nextBigger(num: 513)  // returns 531
nextBigger(num: 2017) // returns 2071

如果无法重新排列数字以形成更大的数字，则返回 -1（或在 Swift 中为 nil）：

9 ==> -1
111 ==> -1
531 ==> -1

（我很确定）我的代码没有错误，唯一的问题是它的效率：

from itertools import permutations

def next_bigger(n):
    possible_nums = [int(''.join(p)) for p in permutations(str(n))]
    possible_nums = list(dict.fromkeys(possible_nums))
    print(possible_nums)
    if possible_nums.index(n)+1 == len(possible_nums):
        return -1
    else:
        return possible_nums[possible_nums.index(n)+1]

我不知道permutation()函数是什么导致了问题，list(dict.fromkeys(possible_nums))但我似乎无法找到一种更有效的方法来查找数字的每个排列n。非常感谢我是否应该重构整个函数或只是替换一些代码以使其更高效！

Answer 1

这是一个众所周知的问题：如何获得下一个词典排列。

你的算法中的问题是你生成所有可能的排列，(O(m!) where m = len(n))并通过list(dict.fromkeys(possible_nums))创建一些字典来处理每个排列，所以总的来说我认为是 O(m * m!) （我没有看过你想用字典做什么，所以我不确定这是否是确切的复杂性，但由于排列，它至少可以肯定O(m!). 没有办法这适用于大输入 - 即多位数，相反，我描述了一种我们可以跳过生成排列的方法！！！

下面的贪心算法实现仅为 O(m)，m = len(n)。

以下答案基于此链接，您可以在其中找到很好的解释和示例代码。

假设我们要计算的数字是： 125330

算法：

1) Find longest non increasing suffix. In our case 5330 is the suffix.
2) Identify pivot i.e the next element after the suffix, here pivot is 2
3) Find rightmost successor to pivot in the suffix, i.e the number in the
   suffix that is greater than pivot, in our example rightmost occurrence of
   number 3 in 5330 is greater than pivot=2.  
4) Swap with pivot, so the number now: 135320
5) Reverse the suffix to get the next smallest permutation: 130235

示例代码：

def next_permutation(num):
    # Find non-increasing suffix
    arr = list(str(num))
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return -1

    # Find successor to pivot
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]

    # Reverse suffix
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return int("".join(arr))

测试用例：

In: 12 Out: 21
In: 513 Out: 531
In: 2017 Out: 2071
In: 9 Out: -1
In: 111 Out: -1
In: 531 Out: -1
In: 144 Out: 414