1

Suppose we have the set $\{1,...,n\}$ and we are given a permutation of its' elements, say for $n=4$ we have $3214$. Then we are given an index $i$ (say indexes go from $1$ to $n$) and we are asked to find the next smallest permutation that is greater than the current permutation, in lexicographical order, where the number at position $i$ in the given permutation is not in its' place. For example, for index $2$ in our given permutation, the next greater permutation where the $2$ is not at position $2$ is $3412$.

I have thought about this and it is easy to just start lexicographically pass on all permutations that are greater than the current one until we reach one where the number at index $i$ is changed. There is an algorithm for that, but that solution is trivial. Is there a way to find it without having to pass over all permutations in between?

TheNotMe
  • 4,841

1 Answers1

1

OK, this is harder than I thought. This is just a partial solution.

Some cases are rather simple.

Case 1: $i$ is currently at location $i$.

If possible, $i$ should be replaced with the smallest digit that is to its right and is larger than it. Then, all digits to the right of position $i$ should be sorted by size.

The problem here occurs if all digits to the right of $i$ are smaller than $i$. In this case, the digits to the left of $i$ will also have to be moved. In this case, we should try to (I think) try to only increase the left neighbor of $i$ by as little as possible, without moving the rest of the left neighbors - this basically takes us back to the starting problem, only $i=i-1$.

Case 2: $i$ is currently not at location $i$. This part, I'm still thinking about.

5xum
  • 123,496
  • 6
  • 128
  • 204