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

Question

我需要输入一个字符串，returns它的下一个字典顺序更大的string.For例如，'anmdfg'的下一个字符串是'anmdgf'。但是，长度输入可能非常大，可能包含100个字符或更多，并且it.So中会有一些重复的字符我决定使用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 不是 sorted.It 似乎我必须生成列表 first.I 尝试过并且它消耗我的内存太快以至于我没有时间终止进程。有什么方法可以让我在不列出列表的情况下对排列结果进行排序吗？

Answer 1

我认为 itertools-y 方法是：

from itertools import dropwhile, permutations

def next_largest(start):
    """Return the next largest permutation of the characters in start."""
    reference = tuple(start)
    try:
        return next(dropwhile(
            lambda p: p <= reference, 
            permutations(sorted(start))
        ))
    except StopIteration:
        raise ValueError('No larger string available')

请注意，您在生成排列之前对 start 进行排序，以确保排列按字典顺序生成。

另请注意：

我已经具体说明了我要捕获的错误，允许发生的任何意外错误正确传播（请参阅 "The evils of except:"）；和

我使用的是 next(thing) 而不是 thing.__next__()（参见）。

Answer 2

真的，真的生成所有小于输出的排列效率低下。最好使用下面实现的 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]

Answer 3

试试这个，

def NextHighestWord(string):
    S = [ord(i) for i in string]
    #find non-incresing suffix from last
    i = len(S) - 1
    while i > 0 and S[i-1] >= S[i]:
        i = i - 1
    if i <= 0:
        return False

    #next element to highest is pivot
    j = len(S) - 1
    while S[j] <= S[i -1]:
        j = j - 1
    S[i-1],S[j] = S[j],S[i-1]

    #reverse the suffix
    S[i:] = S[len(S) - 1 : i-1 : -1]
    ans = [chr(i) for i in S]
    ans = "".join(ans)
    print(ans)
    return True

test = int(input())
for i in range(test):
    s = input()
    val = NextHighestWord(s)
    if val:
        continue
    else:
        print("no answer")

Answer 4

通用方法是：

找到字符串的所有排列作为列表。
对列表进行排序
查找您的项目的索引
然后拿到旁边的物品

下面是实现的代码：

>>> from itertools import permutations

>>> my_string = 'anmdfg'

# Permutation of all the strings
>>> all_strings = list(permutations(my_string, len(my_string)))

# Sorted lexicographically
>>> all_string = sorted(all_strings)

# index of current string
>>> my_index = all_string.index(tuple(my_string))

# Next item (but as tuple)
>>> next_value = all_string[my_index+1]
>>> next_value
('a', 'n', 'm', 'd', 'g', 'f')

# Convert tuple to string
>>> ''.join(next_value)
'anmdgf'

Answer 5

使用 python 生成下一个排列的实现相对简单。

    def nextperm(s):
        l=[]
       for i in range(len(s)):
        l.append(s[i])
       for i in range(-1,-len(s),-1):
         if (l[i] > l[i-1]):
           break
         else:
          pass
       pos=len(s)+(i-1)
      for i in range(pos,len(s),1):
           if (l[pos] > l[i]):
            (l[pos],l[i-1])=(l[i-1],l[pos])
              break
           else:
             pass
      l=l[:pos+1]+l[-1:-(len(s)-pos):-1]  
      s1=''.join(l)
      return(s1)

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

How to get the next lexicographically bigger string in a sorted list by using itertools module?

sorting

algorithm

permutation

python-3.x