Permutation in lexicographic (dictionary) order

Question

Given the following permutation of a,b,c,d,e,f,g,h,i,j, what is the previous permutation in lexicographic (dictionary) order? Write your answer without any blank spaces between letters.

ghadbicefj

I tried and got previous permutation in lexicographic order of "ghadbicefj" to be "ghadbicefj" → "ghadbice fj".

I want to confirm my answer.

Answer 1

You seem to not have made a permutation, but inserted a space. A permutation is where you change the order of the given characters.

The permutations of "abcdefghij" in lexical order start like this:

 abcdefghij
 abcdefghji
 abcdefgijh
 abcdefgihj
 ...

At some point it will reach "ghadbicefj" and the question is to identify which permutation came before it. The order in that "neighborhood" goes like this:

...
ghadbfjeic
ghadbfjice
ghadbfjiec
ghadbicefj
ghadbicejf
ghadbicfej
ghadbicfje 
...

The answer is "ghadbfjiec".

The algorithm to determine it goes as follows:

1. Starting from the right, find the first character that is greater than its successor. If there is none, there is no previous: then the input gives the very first permutation in lexical order. For the example string this character is "i", since it is greater than "c", while "c", "e" and "f" are all less than their successor.

2. Consider the section at the right of that found position. In the example that section is "cefj". We know the characters in that section are sorted in non-decreasing order (because of the previous step). From that section, choose the character that is the greatest among those that are less than the character found in step 1. In the example that is "f".

3. Swap the two found characters. In the example that means we swap "i" and "f". This means that the section of step 2 is still sorted in non-decreasing order. In the example that section has become "ceij". Then reverse that section. In the example that section becomes "jiec".

As you marked this with Python, here is code that implements the above algorithm:

def previous_permutation(s):
    for i in range(len(s) - 2, -1, -1):
        if s[i] > s[i + 1]:
            for k in range(len(s) - 1, i, -1):
                if s[i] > s[k]:
                    return s[:i] + s[k] + s[-1:k:-1] + s[i] + s[k-1:i:-1]

s = "ghadbicefj"
p = previous_permutation(s)
print(p)  # ghadbfjiec