# Lexicographic permutation

Consider that you have a permutation of $$n$$ elements from $$1$$ to $$n$$ and you need to sort the elements lexicographical . for example sorted permutation for $$n=11$$ is $$1,10,11,2,3,4,5,6,7,8,9$$ .Now consider this notation $$Q(n,k)$$ as position of number $$k$$ in lexicographical sorted permutation. $$Q(11,2)=4$$. We are given $$k$$ and $$m$$ we need to find minimum $$n$$ such that $$Q(n,k)=m$$ holds.

I could only find that $$n>=max(m,k)$$ and for next i do not know how to solve it .

First, there is one special case of $$k$$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

• 1 is always at the 1st position.
• 10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
• 100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
• And so on.

We should process this peculiar case first.

The position of $$k$$ in the lexicographically sorted sequence is determined by the numbers that are before $$k$$ (lexicographically). These numbers fall into three categories.

• the numbers that are smaller than $$k$$. If a permutation of 1, 2, ..., $$n$$ contains $$k$$, it must contain all these numbers as well.
• $$k$$ itself.
• the numbers that are bigger than $$k$$.

Let us compute how many numbers before $$k$$ are smaller than $$k$$. For example, take k $$=$$ 619. Any number smaller than $$k$$ has at most three digits.

• All three-digit numbers before 619 constitute the interval [100, 619).
• All two-digit numbers before 619 constitute the interval [10, 61].
• All one-digit numbers before 619 constitute the interval [1, 6].

In total, there are 519 + 52 + 6 $$=$$ 577 numbers that are smaller than 619 and before 619. So if $$m\le$$ 577 + 1, where 1 stands for 619 itself, no $$n$$ can satisfy $$Q(n,\,$$619$$)=m$$. If $$m=$$ 578, the minimum $$n$$ is 619 itself.

Otherwise, the given $$m$$ is bigger than 1 plus the number of numbers smaller than $$k$$ and before $$k$$. We have to include numbers bigger than $$k$$ that are before $$k$$ to increase the position of $$k$$. For the same example, when $$m\gt 578$$, $$n=$$ 619 is not enough.

• Try adding the number between 1000 inclusive and 6190 exclusive.
• If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
• If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
• And so on.