python - 文字列の次に高い辞書順列を見つける

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

次の順列を生成する 1 つの古典的なアルゴリズムは次のとおりです。

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