vicpall's blog

By vicpall, history, 6 years ago, In English

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?

  • Vote: I like it
  • +10
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
6 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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.