## 11071 - Permutation Representation

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### 11071 - Permutation Representation

Because my english is poor ,

"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"

I don't know what is above saying , Can someone give me a example ?

thanks ,
Last edited by SRX on Tue Aug 15, 2006 4:06 pm, edited 1 time in total.
studying @ ntu csie

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### Re: 11071 need some explanations

SRX wrote:

Because my english is poor ,

"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"

I don't know what is above saying , Can someone give me a example ?

thanks ,
Let's put it that way:

> You are given 2 permutations of n elements
> Following some rules you have to transform the first permutation into second

Let's revise those rules by clarifying the example above.
You are given 2 permutations of n elements "12345" and "32514". And you can form the second permutation from the first one by this operation: (53)(51)(54). What this operation tells you to do? It tells you that:

> (54) element 5 goes in a place of 4, element 4 goes in a place of 5
> after (54) you have 12354.
> (51) element 5 goes in a place of 1, element 1 goes in a place of 5
> after (51) you have 52314
> (53) element 5 goes in a place of 3, element 3 goes in a place of 5
> after (53) you have 32514
Thus the first permutation is transformed into second.

In other words operation (x1 x2 x3 ... xn) tells you that you have to shift all elements by one position to the right (ignoring those elements that are not listed in the operation). And (x1 x2 x3 ... xn) ^ p tells you that you have to shift the elements included in operation by "p".

Consider this example:
Operation: (13459)^2
Initial permutation: 13xx45xxx9xx
After operation was performed: 59xx13xxx4xx
Note: All x are NOT to be moved, only those numbers that are included in the operation!

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### Re: 11071 need some explanations

Leonid wrote:
SRX wrote:

Because my english is poor ,

"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"

I don't know what is above saying , Can someone give me a example ?

thanks ,
Let's put it that way:

> You are given 2 permutations of n elements
> Following some rules you have to transform the first permutation into second

Let's revise those rules by clarifying the example above.
You are given 2 permutations of n elements "12345" and "32514". And you can form the second permutation from the first one by this operation: (53)(51)(54). What this operation tells you to do? It tells you that:

> (54) element 5 goes in a place of 4, element 4 goes in a place of 5
> after (54) you have 12354.
> (51) element 5 goes in a place of 1, element 1 goes in a place of 5
> after (51) you have 52314
> (53) element 5 goes in a place of 3, element 3 goes in a place of 5
> after (53) you have 32514
Thus the first permutation is transformed into second.

In other words operation (x1 x2 x3 ... xn) tells you that you have to shift all elements by one position to the right (ignoring those elements that are not listed in the operation). And (x1 x2 x3 ... xn) ^ p tells you that you have to shift the elements included in operation by "p".

Consider this example:
Operation: (13459)^2
Initial permutation: 13xx45xxx9xx
After operation was performed: 59xx13xxx4xx
Note: All x are NOT to be moved, only those numbers that are included in the operation!
tks .

I think "above permutation" is (724) , but it actually means
(
1 2 3 4 5
3 2 5 1 4
)
studying @ ntu csie

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### Re: 11071 need some explanations

a O ( n^2 ) solution is easy to find out , but n<=200000 .

Can someone give me a little hint about what is the
element in element i ' s final position after we do
(123....n)^an (123....n-1)^an-1 .... (123....i+1)^ai+1

thanks .
studying @ ntu csie

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Hmm, yes. This one's getting on my nerves too. Can't think of anything better than O(N^2). A little hint would be very much appreciated...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
A little hint:
If you keep a pointer at the currently last element (elements n, n-1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
If you keep a pointer at the currently last element (elements n, n-1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
Thank you very much , Adrian Kuegel !!!!!!!!!!!!

your hint is great and gives me a good thinking to solve this problem within the time limit , anyway , thanks you again
studying @ ntu csie

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks, Adrian, I think I understand what you mean.
Won't be 'trivial' to implement in C, I fear... realy should learn C++ some day. Or do you have some suggestions on how to do it with 'simple' data structures?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I used a binary tree data structure represented in an array like a heap, so my solution can be implemented easily in C as well.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Thanks Adrian, I finally got it!
Simple enough, indeed, but I never thought of using a heap this way. One learns something everyday!

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
If you keep a pointer at the currently last element (elements n, n-1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
Have I understood right that "a pointer at the currently last element" is a position of element i in a permutation after we have done (12...i+1)^A{i+1}...(12...n)^An and "the number of elements which are in between element i and the currently last element" is a number of positions that is located between "a pointer at the currently last element" and position of element i in result permutation which contains some element from {i + 1,...,n}?

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
well... got AC using BST, but i cant understand idea of heap.

anyway,

here r 3 cases for fellows:

Code: Select all

``````10
1 2 3 4 5 6 7 8 9 10
5 4 1 9 8 10 3 2 6 7

4
1 2 3 4
3 4 1 2

5
1 2 3 4 5
5 4 2 3 1``````
Output

Code: Select all

``````0 1 1 3 4 0 3 7 1 4
0 0 0 2
0 0 1 3 4
``````
Self judging is the best judging!

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
Input:
3
1 2 3
3 2 1
3
1 2 3
2 1 3
4
1 2 3 4
4 2 1 3
3
1 2 3
3 1 2
4
1 2 3 4
2 4 1 3
4
1 2 3 4
4 1 2 3
3
1 2 3
2 3 1
7
1 2 3 4 5 6 7
6 5 1 7 2 4 3
7
1 2 3 4 5 6 7
2 4 5 6 7 3 1
6
1 2 3 4 5 6
3 5 1 4 6 2
9
1 2 3 4 5 6 7 8 9
2 4 9 8 7 1 3 6 5
10
1 2 3 4 5 6 7 8 9 10
1 6 7 3 9 8 4 2 5 10
10
1 2 3 4 5 6 7 8 9 10
4 5 10 6 8 3 2 7 9 1
10
1 2 3 4 5 6 7 8 9 10
9 2 1 7 8 6 3 4 5 10
6
1 2 3 4 5 6
6 4 1 2 3 5
Output:
0 1 2
0 1 0
0 1 0 3
0 0 2
0 1 1 2
0 0 0 3
0 0 1
0 0 2 1 4 2 3
0 0 2 0 0 0 2
0 0 1 2 2 1
0 1 1 2 4 3 6 7 6
0 1 0 1 1 0 1 7 4 0
0 1 2 0 0 2 4 3 3 7
0 1 0 0 2 5 0 4 8 0
0 0 0 3 0 5

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
``````struct node {