Algorithm: How to find the next lexicographic permutation

Briefly describe what the lexicographic order is - sorting in alphabetical order. Those. the sequence of characters - AAA → AAB → AAC → AAD → ... ... ... WWW - is sorted alphabetically (or in our case lexicographical) order.

Imagine that you have a finite sequence of characters, for example, 0, 1, 2, 5, 3, 3, 0 and you need to find all possible permutations of these characters. The most intuitive, but also the greatest in complexity, is the recursive algorithm, when we select the first character from the sequence, then recursively select the second, third, etc., until all the characters from the sequence are selected. It is clear that the complexity of this algorithm is O (n!).

But it turns out that the simplest algorithm for generating all permutations in the lexicographical order is to start with the smallest and repeatedly calculate the next permutation in place. Let's see how to do it.

Just as when calculating the next integer value, we should try to increase the right side of the sequence and leave the left side unchanged.

As an example, take the above sequence - (0, 1, 2, 5, 3, 3, 0). To get the sequence above the original, it is enough to rearrange the first and second elements in places, but this is not necessary, since you can rearrange the second and the third and get a closer sequence in ascending order. which will lead us to the next closer permutation and so on.

The most optimal algorithm in this case is the following:

1. First of all, you must find the largest non-increasing suffix. In the above example, this will be - (5, 3, 3, 0). If you try to make any permutation in this sequence, it will not be higher than the original one.
   It is worth saying that you can find this sequence in O (n) time, looking through the sequence from left to right.
2. The next element from the suffix is ​​a pivot point. In our case, it is 2. The turning point will always be less than the first element of the suffix. This means that the suffix will necessarily have an element that exceeds the turning point and if we change the turning point to the smallest element from the suffix that exceeds the reference element of the turning point - we will get a sequence that exceeds the original - in our case it will be - (0, 1, 3, 5 3, 2, 0).
   Those. the result of this operation will be the minimum possible prefix in ascending order.
   
3. And in the last step, we must sort the suffix in ascending order. Those. we get the lowest possible suffix. In our example, this will be (0, 2, 3, 5) and the whole sequence will look like (0, 1, 3, 0, 2, 3, 5).
   

This value will be the next lexicographic permutation.



As for the practical application of the algorithm, I have never needed it for the whole time of my work, but they did not consider the interview in Uber :))

For simplicity, all the code will be written in Go and I think it would be difficult for anyone to translate it into any other programming language .

Many thanks to PYXRU and 646f67 , which poked my nose at the possible optimization of the algorithm — to calculate the permutation for the linear complexity simply by making a reverse suffix.

funcNextPermutationAlgorithm(w string)string {
 l := len(w)
	b := []byte(w)
	r := "no answer"for i:=l-1; i>0 ; i--{
		if b[i-1] < b[i] {
			pivot := i
			for j := pivot; j < l; j++ {
				if b[j] <= b[pivot] && b[i-1] < b[j] {
					pivot = j
				}
			}
			b[i-1], b[pivot] = b[pivot], b[i-1]
			for j := l-1; i < j; i, j = i+1, j-1 {
				b[i], b[j] = b[j], b[i]
			}
			r = string(b)
			break
		}
	}
	return r
}