How does this algorithm for generating the next lexicographically ordered permutation work?

Question

This is the step by step process I found for ordering lexicographical permutations:

1. Take the previously printed permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘first character’.

2. Now find the ceiling of the ‘first character’. Ceiling is the smallest character on right of ‘first character’, which is greater than ‘first character’. Let us call the ceil character as ‘second character’.

3. Swap the two characters found in above 2 steps.

4. Sort the substring (in non-decreasing order) after the original index of ‘first character’.

Source: http://www.geeksforgeeks.org/lexicographic-permutations-of-string/

I have already written my Pseudo-code for it,and am about to start programming it now as well. I understand what is happening in the Algorithm, but I am not sure why it works. Like on Step 2 why must the ceiling character be "the smallest character on right of ‘first character’, which is greater than ‘first character'". I understand that it doesn't work if you don't do it this way, but I don't understand why it does work when you do.

If someone could explain to me why you need to each step in the algorithm that would be great and it would make me far more comfortable in starting my code.

Edit: I should mention I understand why you rearange the substring into acsending order, as to find the smallest permute, what I dont understand is the step 1 and 2 as to why you swap the ceiling and the first charector

Answer 1

Basically we want to increase the first character we can from the right by the smallest possible amount and make the smallest possible permutation (we'll get to how we do this) with the characters remaining to the right of it. Why this is what we want to do is, I hope, pretty logical. If it isn't, it may help to think in terms of a permutation of digits (making a number) - you could keep adding one to the number until you get to another permutation of that number, though a way more efficient method would be to magically find the left-most number we need to increase and the amount to increase it by and simply get the smallest permutation of the digits to the right, which is exactly what this algorithm does.

Well, we can't just increase a character to any other character, it needs to be a character that already exists in the permutation. And if this character exists to the left, that won't really help, as it will require changing the character that's to the left as well, which will have us potentially end up with a much larger permutation. So we need to use a character to the right and, on top of this, it must be the smallest character that is bigger than this character.

So, go from the right and, for each character A, look right for the smallest character larger than A (call this B). If you don't find one, try the next character. The above paragraph explains that we want to increase A to B's value. Once we've done this, we are left with 2 B's, now, to fix this, we decrease B to A's value (this is essentially just swapping A and B). From here we fix everything to the right of where A was. Since we're going to do this fixing, it doesn't really matter that the new A now might not be where it should be).

How do we fix the remaining characters? Well, we want the smallest permutation of them, which is simply those characters ordered.

That takes care of steps 2-4.

What about step 1? This is actually just an optimization of the algorithm. If we're going from the right and finding the first character for which there exists a larger character to the right, won't it make sense that we need to find the first character that's smaller than a character to the right of it, or, more specifically, the character one position to the right of it? Think about 987654321 - we can't do anything here since all the characters are larger than the characters directly to their right.

To explain with an example:

Take ABDC.

The first character for which there exists a larger character to the right is B. The smallest character larger than B is C.

So the next possible permutation will look like: AC?? (? is unknown)

The two remaining characters are D and B, which we need to find the smallest permutation of, which is BD. So we put it together: ACBD.

In terms swapping B and C - we need B to become C (from paragraph 2), but there still needs to be a B in the string for it to be a valid permutation (so we can't just replace B with C) and it doesn't matter where B ends up, since, right afterwards, we find the smallest permutation of the remaining characters.

Answer 2

Helpful link on permutations - the algorithm is explained there.

I also had hard time understand the logic, so here is my take on in with high level overview.

Basically the sequence of elements (characters/numbers..) you permutate can be divided into to two sections - the prefix and the suffix. The suffix is everything from right up to the "first character".

The algorithm "increases" the prefix by swapping the "second character" (which is in the suffix and is the smaller of the swapped elements) with the "first character" (which is the right-most element in the prefix and is the bigger one). The "second character" and "first character" are chosen in a way to represent the smallest possible increase in the prefix.

By having the smallest possible increase (done with a swap operation) in the prefix you can say that transforming the sequence from increasing (first permutation) to decreasing (last permutation) you get "all" the possible sequences of those elements.

Why is the suffix being sorted after the swap? To make the suffix "as small as possible" so we don't have to increase the "current" prefix in the next few iterations (by current prefix I mean the prefix in this step of algorithm)

Answer 3

The main idea in this algorithm is how to find the next permutation for a given permutation. According to the link that you wrote, it can be done by finding the right most character in the last printed permutation that is smaller than its right character.

Proof:

Denote P = P[1]p[2]p[3]..p[n] as the last printed permutation. Suppose k is the index of the rightmost character such P[k] > P[k+1].

According to the definition of Next, So Next(P) = P[1]p[2]p[3]..p[k+1]p[k]p[k+2]p[k+3]..p[n].

Let's assume that there is P' such value(P) < value(P') < value(Next(P)).

Denote k' as the minimal index such P[k'] != P'[k'].

There are 3 options:

• k' < k: In that case, because value(P') > value(P) , we get that P'[k'] > P[k']. But until the k' index, Next(P) and P are the same, so P'[k'] > Next(P)[k'] and until the k' they are same (because k' < k) => in contrast to the fact that value(P') < value(Next(P)).

• k' > k: P'[k'] > P[k'] because value(P') > value(P), but we know that until the k' P and P' are the same, so there is k'' > k' such that P[k''] < P[k'] in contrast to the the definition of Next (to the fact that k is the right most that P[k] < P[k+1]). That because we can find two neighbors X,Y in the chain P[k']P[k'+1]..P[k''] such X < Y.

• k' = k': if Next(P)[k'] < P'[k] we will get that value(P') > value(Next(P)) that is not true. If P'[k] = Next(P)[k], because k is the rightmost and because value(P') <= value(Next(P)) we get that P' = Next(P) which can't be true because value(Next(P)) > value(P'). And if P'[k] < Next(P[k]) it can't be similarly to option 2.

So we get that such P' is not possible => Next(P) is the next permutation to P as we wanted.

Example: P = "DFEBCA" Next(P) = "DFECBA".

So k = 4, because 4 is the rightmost index such P[i] < P[i+1].

If you try to find other permutation P' such value(P) < value(P') < value(Next(P)) You won't find.

Answer 4

To print the next lexicographical term of a word we need to follow the algorithm as stated below:-->

1. Calculate the length of the word and make your pointer point to last and second last character of the word. If the second last character is smaller then the last character then swap the two characters. It is the required answer.
2. If the case 1st does not occur then make your second last pointer (say i) decrement by one and search for the character which is greater then the character at with location but smallest in the substring which is on the right. If such a character is found then swap with location character with the found ceiling character (one found on right).
3. Now, finally sort the substring on the right of pointer i else repeat step two.