查找字符串的下一个最高词汇排列

Question

给定一个字符串W，我想实现它的下一个字符串在字典上更大。在

eg 1:
givenstring = "hegf"
nexthighest = "hefg"

我现在所做的一切都在这里

^{pr2}$

因为这不是解决这个问题的有效方法。你能给我提个更好的解决这个问题的办法吗

Answer 1

这是解决这个问题的另一种方法

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 2

生成下一个排列的一个经典算法是：

Step 1: Find the largest index k, such that A[k] < A[k + 1]. 
        If not exist, this is the last permutation. (in this problem just reverse the vector and return.)
Step 2: Find the largest index l, such that A[l] > A[k] and l > k.
Step 3: Swap A[k] and A[l].
Step 4: Reverse A[k + 1] to the end.

这是我上面的算法的C++片段。虽然不是python，但语法简单，伪代码一样，希望你能理解。在

^{pr2}$