Найти следующую наивысшую лексикографическую перестановку строки

учитывая строку 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])

так как это не эффективный способ решить эту проблему. не могли бы вы предложить мне лучший способ решить эту проблему


python algorithm lexicographic-ordering
person Syed Munawwar    schedule 17.11.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

вот еще один способ решить эту проблему

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")
person Rehan Shikkalgar    schedule 17.11.2016
comment
дополнительные пояснения см. на этом веб-сайте — nayuki.io/page/next-lexicographical-permutation -алгоритм - person Rehan Shikkalgar; 17.11.2016
comment
Спасибо за помощь - person Syed Munawwar; 17.11.2016

arrow_upward
0
arrow_downward

Один классический алгоритм для создания следующей перестановки:

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.

Вот мой фрагмент С++ вышеприведенного алгоритма. Хотя это не 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());
}
person Kaidul    schedule 17.11.2016