The Gateway to Computer Science Excellence
+18 votes
1k 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 by Boss (30.1k points)
recategorized by | 1k 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

3 Answers

+28 votes
Best answer

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.7k 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
0
I am getting sorted array as well.
0

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.

+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.7k 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.

So Answer is option B.

by (31 points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,461 answers
195,358 comments
100,245 users