查找给定字符串的下一个更大排列的算法

Question

我想要一个有效的算法来找到给定字符串的下一个更大的排列。

Answer 1

我们按照以下步骤查找下一个词典编排：

nums = [0,1,2,5,3,3,0]

nums = [0]*5

curr = nums[-1]

pivot = -1

for items in nums[-2::-1]:

    if items >= curr:

        pivot -= 1

        curr = items

    else:

        break

if pivot == - len(nums):

    print('break')     # The input is already the last possible permutation

j = len(nums) - 1

while nums[j] <= nums[pivot - 1]:

    j -= 1

nums[j], nums[pivot - 1] = nums[pivot - 1], nums[j]

nums[pivot:] = nums[pivot:][::-1]

> [1, 3, 0, 2, 3, 5]

因此，想法是：想法是遵循步骤-

从数组的末尾找到索引“ pivot”，使nums [i-1] <nums [i]

查找索引j，使得nums [j]> nums [pivot-1]

交换这两个索引

从枢轴开始反转后缀