906 views

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?

1. $B$ will be a sorted array.
2. $B$ is a permutation of array $A$.
3. Doing the same transformation twice will not give the same array.
4. $B$ is not a permutation of array $A$.
5. None of the above.
in DS
recategorized | 906 views
0
Good question. ?
0
It consists of a permutation of numbers 1....n1....n wht does it mean

@Bikram sir
+2

It consists of a permutation of numbers 1....n1....n wht does it mean

It means all the different permutations of n numbers.

see the best answer, example is given.

0

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

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.

by Boss (22.4k points)
edited by
0
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
0
nice sagar sir
0
+1 vote

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

by Active (2.6k points)
+1 vote

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.

by (31 points)
edited

–1 vote
1