algorithm - 如何使用 itertools 模块获取排序列表中下一个字典序更大的字符串？

Question

我需要输入一个字符串，并返回它的下一个字典序更大的字符串。例如，'anmdfg'的下一个字符串是'anmdgf'。但是，输入的长度可能非常大，可能包含 100 个字符或者更多，并且其中会有一些重复的字符。所以我决定使用 itertools.permutations 而不将其放入列表中，以避免内存过度消耗。

#!/usr/bin/env python3
from itertools import permutations

a = list(input())
tuple_a = tuple(a)
b = permutations(a,len(a))
p = next(b)
result = ''

try:
    while 1:
        p = next(b)        
        if p > tuple_a:
            result = ''.join(p)
            print(result)
        break

except:
    if result == '':
        print('No answer.')
else:
    if result == '':
        print('No answer.')

我的样本中的 b 没有排序。看来我必须先生成列表。我试过了，它消耗我的内存太快了，我来不及终止进程。有什么方法可以让我在不列出列表的情况下对排列结果进行排序吗？

Answer 1

生成小于输出的所有排列的效率确实真的很低。最好使用 classic linear-time algorithm实现如下:

def nextperm(lst):
  for i in range(len(lst) - 1, 0, -1):
    if lst[i-1] < lst[i]:
      for j in range(len(lst) - 1, i-1, -1):
        if lst[i-1] < lst[j]:
          return lst[:i-1] + lst[j:j+1] + lst[:j:-1] + lst[i-1:i] + lst[j-1:i-1:-1]