使排列函数更有效

Question

我正在解决一个代码战争套路问题，但我正在努力弄清楚如何使我的功能更高效，因为我一直卡在涉及大量测试的测试用例上。

套路说明如下：

Create a function that takes a positive integer and returns the next bigger number that can be formed by rearranging its digits. For example:
12 ==> 21
513 ==> 531
2017 ==> 2071
nextBigger(num: 12)   // returns 21
nextBigger(num: 513)  // returns 531
nextBigger(num: 2017) // returns 2071
If the digits can't be rearranged to form a bigger number, return -1 (or nil in Swift):
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)。

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

假设我们要计算的数字是：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

使排列函数更有效

Making a permutations function more efficient

python

algorithm

performance

permutation

python-3.x