使置换函数更有效

Question

我正在解决一个代码战争问题，但我正在努力找出如何使我的函数更有效，因为我一直被涉及大量数据的测试用例所困扰

kata的说明如下：

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

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

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