Problem solving with programming: Ambiguous permutations
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 anambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?
The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.
http://codehob.blogspot.com/2015/04/spoj-problem-permut2-ambiguous.html
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 anambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?
The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.
| bool isAmbiguous(vector<int>& arr) { | |
| int i; | |
| vector<int> inverse(arr.size()); | |
| for( i = 0; i < arr.size(); i++ ) | |
| { | |
| inverse[arr[i]-1] = i+1; | |
| } | |
| for( i = 0; i < arr.size(); i++ ) | |
| { | |
| if( arr[i] != inverse[i] ) | |
| return false; | |
| } | |
| return true; | |
| } |
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(br.readLine());
while(n!=0){
int per[]=new int[n+1];
int inper[]=new int[n+1];
String str[]=br.readLine().split(" ");
for(int i=1;i<=n;i++){
per[i]=Integer.parseInt(str[i-1]);
inper[per[i]]=i;
}
boolean isAmbigous=true;
for(int i=1;i<=n;i++){
if(per[i]!=inper[i]){
isAmbigous=false;
break;
}
}
Read full article from Problem solving with programming: Ambiguous permutations