Ambiguous Permutations - Explain the statement

general
,
6

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

7

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.

1 Like
8

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

9

thankyou geeks for your answers ,It is really helpful forum

3 Likes
10

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;
}
11

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 :- 2Pdt6z - Online C++0x Compiler & Debugging Tool - Ideone.com

4 Likes
12

what all that is essayleaks i cann’t understand.

13

Thanks a lot for the explanation

14

what happens if the size were given like this
4
1 15 3 2?
what will be the o/p?

15

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

16
17
18
19

@axuma thats good

1 Like
20

Hahaha, thx man :).

21

Best explanation for this one! Thanks! :smiley:

22

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

23

best answer for this question

24

best explanation so far…XD
:blush::blush:

25

best explained buddy thanku