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?
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:
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-1] = 1 —> invP = 1;
invP[p-1] = 2 —> invP = 2;
and so on…
This way, you see it’s easy to construct inverse permutation from the given permutation
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
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.
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.