TIFR CSE 2011 | Part B | Question: 30

Question

Consider an array $A[1...n]$. It consists of a permutation of numbers $1....n$. Now compute another array $B[1...n]$ as follows: $B[A[i]]:= i$ for all $i$. Which of the following is true?

• A. $B$ will be a sorted array.
• B. $B$ is a permutation of array $A$.
• C. Doing the same transformation twice will not give the same array.
• D. $B$ is not a permutation of array $A$.
• E. None of the above.

Comments

For anybody who's still curious as to what is 'permutation of elements, its just one of the random arrangements of the n elements.

https://gateoverflow.in/260210/permutations-tifr2011-b-30

---

@Mizuki

Thank You Very Much :)

---

the link which you provided shows page not found. Please update the link. @Muzuki

Answer 1

Option (b) B is a permutation of array A.

In fact, $B$ gives the reverse index of all the elements of array $A$. Since the array $A$ contains numbers $[1 .. n]$ mapped to the locations $[1 .. n]$ and $A$ is a permutation of the numbers $[1 .. n]$, the array $B$ will also be a permutation of the numbers $[1 .. n]$.

For example: $$\begin{array}{l|cccccccc} \text{index} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\[1em] \hline A & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4\\ B & 2 & 6 & 3 & 8 & 1 & 5 & 4 & 7 \end{array}$$

---

To see that option c is incorrect, let array $C$ be the array attained from doing the same transformation twice, that is, $C[B[i]] = i , \forall i \in [1 .. n]$. We get, $$\begin{array}{l|cccccccc} \text{index} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\[1em] \hline A & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4\\ B & 2 & 6 & 3 & 8 & 1 & 5 & 4 & 7\\ C & 5 & 1 & 3 & 7 & 6 & 2 & 8 & 4 \end{array}$$

We can see that $C = A$, which makes option c incorrect.

Comments

Hi,

Could you please elaborate on How Array A contains 5,1,2 ... sequence ? Is it random sequence of numbers which we got after permutations of 8 elements ?

Thanks

---

nice sagar sir

---

this link will help 

https://www.geeksforgeeks.org/check-if-two-arrays-are-permutations-of-each-other/

 

---

I am getting sorted array as well.

---

In example, $\mathbf 1$ in front of $\mathbf 2$ at index $\mathbf 2$, I think $\mathbf 5$ should come.

@techbd123

Can you check this once, please.

Answer 2

let n=2
A[1,2] and it consists of a permutation of numbers 1,2 which are 
case 1: (1,2)
case 2: (2,1)
B[A[i]]:=i  for all i (GIVEN)
case 1: B[A[1]]:=1 B[1]:=1
             B[A[2]]:=2 B[2]:=2 so B=(1,2)
case 2: B[A[1]]:=1 B[2]:=1
             B[A[2]]:=2 B[1]:=2 so B=(2,1)
Hence array B have permutation of 1,2

Ans is B

 

Answer 3

Let n=4 ,so indexes from 1 to 4.

Ex 1 - A[3,2,1,4] then B is B[3,2,1,4]

Ex 2 - A[4,2,1,3] then B is B[3,2,4,1]

From the examples above

Option C - Doing the same transformation twice will not give the same array. is proven false by Ex 1. As A=B.

Option A - B will be a sorted array. is proven false by Ex 2.

Option B - B is a permutation of array A.

From google - meaning of permutation - "each of several possible ways in which a set or number of things can be ordered or arranged.". As we see both Ex 1 and Ex 2 B's are permutations of their A's.

Option D - is false if option B is True.

So Answer is option B.

Answer 4

Given that array is start from 1 to n

let assume A[i] = x; therefore where can be this x in sorted array ? it is at xth position

B[x]=x but we are getting B[x]=i ===> option A is wrong

Note that A[i] given different results because of no repetition of numbers.. that implies every index of B is accessed and moreover we fill the index of B with i which is different ===> B contains the permutation order of A

Comments

option b is right??