Find next highest lexicgraphic permutation of a string

Question

given a string W, what i want to achieve its next string lexicographically greater.

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

what i have tried till now is here,

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

since this is not the efficient way to solve this. can u please suggest me better way to solve this problem

Rehan Shikkalgar · Accepted Answer · 2017-02-03T10:33:46.233

1

here is another way to solve this problem

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

edited Feb 03 '17 at 10:33

answered Nov 17 '16 at 08:02

Rehan Shikkalgar

1,029
8
16

for more explanation see this website - https://www.nayuki.io/page/next-lexicographical-permutation-algorithm – Rehan Shikkalgar Nov 17 '16 at 08:03
1

thanks for helping me – Syed Munawwar Nov 17 '16 at 08:06

score 0 · Answer 2 · answered Nov 17 '16 at 08:03

One classic algorithm to generate next permutation is:

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.

Here is my C++ snippet of above algorithm. Though its not python, the syntax is simple and pseudo-code alike, hope you will get the idea.

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

2 Answers2