让换位功能更高效

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