如何通过使用itertools模块获取排序列表中的下一个按字典顺序大的字符串？

一尘不染

如何通过使用itertools模块获取排序列表中的下一个按字典顺序大的字符串？

algorithm

我需要输入一个字符串，并返回其在字典上大的下一个字符串。例如，下一个字符串“ 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未排序，似乎我必须首先生成列表，我尝试了一下，它消耗了我的内存，以至于我没有时间终止该过程。我有什么办法可以在不列出列表的情况下对排列结果进行排序？

阅读 182

2020-07-28

共1个答案

一尘不染

这是真的， 真的很
低效的产生所有排列小于输出。最好使用以下实现的经典线性时间算法：

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]

2020-07-28