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

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])

因为这不是解决这个问题的有效方法。你能建议我更好的方法来解决这个问题

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());
}

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

Find next highest lexicgraphic permutation of a string

python

algorithm

lexicographic-ordering