I'm trying to solve the following problem: "We call a permutation a set of 2*n numbers (A[1], A[2], ... , A[n], A[n+1], A[n+2], ... , A[2*n]) such that: a) A[1]<A[2]<...<A[n] b) A[n+1]<A[n+2]<...<A[2*n] c) A[1]<A[n+1], A[2]<A[n+2],... A[n]<A[2*n]
There are 2 types of questions: a) given the size of the permutation (n), and the permutation itself, find the position of the permutation (see the example below) b) given the size of the permutation (n) and a number i, find the ith permutation
For example, if n=3 the permutations are: 1 2 3 4 5 6, 1 2 4 3 5 6, 1 2 5 3 4 6, 1 3 4 2 5 6, 1 3 5 2 4 6.
So, if the type of the question is a), n is 3 and the permutation is 1 3 4 2 5 6, then the answer is 4. If the type of the question is b), n is 3 and i is 4, then the answer is 1 3 4 2 5 6."
Can you help me, at least give me a hint?
The problem is, You should select n numbers from 1 to 2n. But for every i the number of selected numbers should not be less than unselected numbers. I don’t know the limits bu the solution looks like dynamic programming. dp[i][j] means I am at i th number. And I have selected j numbers.
You can make an observation that number of "special" permutations is a Catalan number. Therefore, you can think of finding parallels with parenthesis sequences. The first half is positions of opening parentheses, and the second — of closing. That way, 134256 corresponds to ()(()). You can easily convert both ways.
Answering those questions for parenthesis sequences is a well-known problem. First question can be read as "Find the number of a given parenthesis sequence in lexicographical order", second is just the first reversed.
More about that on StackExchange.