Ambiguous Permutations - Explain the statement

general
,
1

I have been trying to understand the meaning of the problem statement of Ambiguous Permutations for some time. But I still haven’t been able to figure out what are the various types of permutations given in the statement. The given examples are not clear and are too short for recognizing the pattern specified.

This sentence is not clear.

You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.

How is this inverse permutation formed by the given permutation

2, 3, 4, 5, 1

Can someone please explain the problem statement and perhaps edit it to add clarity?

@Admin

2

Hello @anshbansal,

It is only a matter of “playing around” with the 1-based indexes of a given permutation to obtain the called inverse permutation.

Let’s work trough your example:

Original sequence
2,3,4,5,1

The mapping between the sequence and the 1-based indexes is:

Element —> 1-based Index

2 —> 1

3 —> 2

4 —> 3

5 —> 4

1 —> 5

Now, suppose we call to the array that holds the original permutation, p and denote it’s i-th element as p[i], obviously on 0 indexed notation.

To build the inverse permutation, we can create new array called invP, and denote its i-th element on 0-indexed notation as invP[i].

It’s easy to see that:

invP[p[i]-1] = i+1;

so, we have:

invP[p[0]-1] = 1 —> invP[1] = 1;

invP[p[1]-1] = 2 —> invP[2] = 2;

and so on…

This way, you see it’s easy to construct inverse permutation from the given permutation :smiley:

Also, the statement is clear in my opinion, I guess that good interpretation and careful reading are also part of a good problem. Then the additional “trick” or complication is to be careful with the 1-based index versus 0-based index, but, such trick is also part of the problem and it is there to make it slightly more interesting :slight_smile:

Best regards,

Bruno

5 Likes
3

@kuruma tnx, appreciate your help. i see your posts everywhere.

4

http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/lecture-5-transposes-permutations-spaces-r-n/

5

http://www.maximumpc.com/forums/viewtopic.php?f=23&t=19928

6

example input:

input: 
4
1 4 3 2
5
2 3 4 5 1
1
1
7
6 3 7 2 1 4 5
5
4 1 3 2 5
5
1 3 5 4 2
5
2 5 3 1 4
5
2 5 1 3 4
0

output: 
ambiguous
not ambiguous
ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
7

Regular permutations. Examples…
1 2 3 4 5
3 2 5 4 1
4 3 1 5 2

Inverse Permutations. These are based on a regular permutation and tell you where the number at a given index is located in the regular permutation. Examples... 

reg: 1 3 2 inv: 1 3 2 
reg: 2 3 1 inv: 3 1 2 
reg: 2 1 3 5 4 inv: 2 1 3 4 5 
reg: 1 inv: 1 

Ambiguous Permutations. These are permutations where the regular and inverse permutation are the same. 

reg 1 2 3 inv 1 2 3 - ambiguous 
reg 3 2 1 inv 3 2 1 - ambiguous 
reg 1 3 2 inv 1 3 2 - ambiguous 
reg 3 1 2 inv 2 3 1 - not ambiguous 

Input file format: 
3 - permutation size 
1 2 3 - permutation 
3 - permutation size 
2 1 3 - permutation 
0 - input terminator
2 Likes
8
9

Example: 1 6 3 4 2 5

You have that permutation of 6 numbers(from 1 to 6).

Now, for the inverse you start looking from 1 to 6 the numbers in the example, I mean:

The number 1 in wich position is located at 1 6 3 4 2 5?
It is located first. So, the first number in the inverse is 1.

Inverse so far: 1XXXXX

The number 2 in wich position is located at 1 6 3 4 2 5?
It is located 5th. So, the second number in the inverse is 5.

Inverse so far:15XXXX

.

.

.

The number 6 in wich position is located at 1 6 3 4 2 5?
It is located 2nd. So, the 6th position in the inverse is 2.

Inverse so far:153462

This means this permutation is not ambiguous. Because 1 6 3 4 2 5 !=1 5 3 4 6 2.

Now, with 1 4 3 2(from 1 to 4)

In wich position is located 1 at 1 4 3 2. It’s first, so the first number in the inverse is 1

In wich position is located 2 at 1 4 3 2. It’s 4th, so the second number in inverse is 4

In wich position is located 3 at 1 4 3 2. It’s 3rd, so the third numberse in the inverse is 3

In wich position is located 4 at 1 4 3 2. It’s 2nd, so the fourth number in the inverse is 2

1 4 3 2 = 1 4 3 2, so this is an ambiguos permutation.

Notice that you need start looking from 1 until n.

6 Likes
10

@axuma thats good

1 Like
11

Hahaha, thx man :).

12

tell some critical cases to test my problem…my code is working right for sample input,so provide some difficult test cases

13

Best explanation for this one! Thanks! :smiley:

14

very nice explanation for this question.Thanks for it…
:slight_smile:

15

You can also think of an array as sorted index associated with value.
For example, array = 1,6,3,4,2,5
You have index 0,1,2,3,4,5

0 is connected to 1

1 is connected to 6

2 is connected to 3

3 is connected to 4

4 is connected to 2

5 is connected to 5

You have left side sorted (the index). Now, you wanna sort the array by its value and let the index be the value itself!

That’s your task! After sorting, you will have index 0,4,2,3,5,1 as the answer, add one to them to turn them into 1-based index. 1,5,3,4,6,2

And that’s the secret.

The other way is to think of the word INVERSE without thinking too much, just use b[a[i]] = i; And b will be the inverse array, of course you have to change the index to 1-based first. You can simply allocate an array of size n+1 and ignore the first 0-th index for simplicity.

16

Basically it says that an Inverse Permutation is the one where the ith number is the position of the the number i in the array
for eg:
Perm: 1 3 5 4 2
InvPerm: 1 5 2 4 3

17

thankyou geeks for your answers ,It is really helpful forum

3 Likes
18

pls, tell if my code is correct or not… and thnx
(sorry for any stupidity, just started learning code)

#include <stdio.h>

int read()
{
char i, num=0;
for(;;){
    i=getchar();
    if(i=='\n' || i==' ') break;
    num=num*10+i-'0';
   }
return num;
}

int main()
{
int arr[100010], arro[100010], n, i, num;
while(1){
    n=read();
    if(n==0) break;
    for(i=0;i<n;i++){
        num=read();
        arro[i]=num;
        arr[num-1]=i+1;
      }
    for(i=0;i<n;i++){
        if(arro[i]!=arr[i]){
            num=200000;
            break;
          }
      }
    if(num==200000) printf("not ambiguous\n");
    else printf("ambiguous\n");
}
return 0;
}
19

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index ‘i’ indicates that the number ‘i’ is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation.

here is the code for it :- http://ideone.com/2Pdt6z

4 Likes
20

what all that is essayleaks i cann’t understand.