查找字符串的下一个最高字母序列排列

Question

给定字符串W，我想实现其下一个字符串的字典顺序更大。

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

我曾尝试到现在就在这里，

from itertools import permutations 
q = int(input()) 
for i in range(q): 
    s = input() 
    if s == s[::-1]: 
     print("no answer") 
    else: 
     x = ["".join(p) for p in list(permutations(s))] 
     x.sort() 
     index = x.index(s) 
     print(x[index+1]) 

，因为这不是解决这个的有效途径。 u能请建议我更好的办法来解决这个问题

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，但它的语法很简单，伪码很相似，希望你能明白。

void nextPermutation(vector<int> &num) { 
    int k = -1; 
    int l; 
    //step1 
    for (int i = num.size() - 1; i > 0; --i) { 
     if (num[i - 1] < num[i]) { 
      k = i - 1; 
      break; 
     } 
    } 
    if (k == -1) { 
     reverse(num.begin(), num.end()); 
     return; 
    } 

    //step2 
    for (int i = num.size() - 1; i > k; --i) { 
     if (num[i] > num[k]) { 
      l = i; 
      break; 
     } 
    } 
    //step3 
    swap(num[l], num[k]); 

    //step4 
    reverse(num.begin() + k + 1, num.end()); 
}