Generating Permutations Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Generating Permutations”.

1. The dictionary ordering of elements is known as?
a) Lexicographical order
b) Colexicographical order
c) Well order
d) Sorting
View Answer

Answer: a
Explanation: Lexicographical order is also known as dictionary order. It is a generalized method of the way words are alphabetically ordered in a dictionary.

2. How many permutations will be formed from the array arr={1,2,3}?
a) 2
b) 4
c) 6
d) 8
View Answer

Answer: c
Explanation: No.of permutations for an array of size n will be given by the formula nPn. So for the given problem, we have 3P3=6 or 3!=6.

3. What will be the lexicographical order of permutations formed from the array arr={1,2,3}?
a) {{2,1,3},{3,2,1},{3,1,2},{2,3,1},{1,2,3},{1,3,2}}
b) {{1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,2,1},{3,1,2}}
c) {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}
d) {{2,1,3},{3,1,2},{3,2,1},{2,3,1},{1,2,3},{1,3,2}}
View Answer

Answer: c
Explanation: The number of permutations for the problem will be 6 according to the formula 3P3. When ordered in lexicographical manner these will be {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.
advertisement
advertisement

4. What is the name given to the algorithm depicted in the pseudo code below?

```procedure generate(n : integer, Arr : array):
if n = 1 then
output(Arr)
else
for i = 0; i <= n - 2; i ++ do
generate(n - 1, Arr)
if n is even then
swap(Arr[i], Arr[n-1])
else
swap(Arr[0], Arr[n-1])
end if
end for
generate(n - 1, Arr )
end if```

a) bubble sort
b) heap sort
c) heap’s algorithm
d) prim’s algorithm
View Answer

Answer: c
Explanation: The given algorithm is called Heap’s algorithm. It is used for generating permutations of a given list.
Note: Join free Sanfoundry classes at Telegram or Youtube

5. Heap’s algorithm requires an auxiliary array to create permutations.
a) true
b) false
View Answer

Answer: b
Explanation: Heap’s algorithm does not require any extra array for generating permutations. Thus it is able to keep its space requirement to a very low level. This makes it preferable algorithm for generating permutations.
advertisement

6. What is the time complexity of Heap’s algorithm?
a) O(n log n)
b) O(n2)
c) O(n*n!)
d) O(n!)
View Answer

Answer: d
Explanation: The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). It is calculated by using substitution method. It is found to be equal to O(n!).

7. What will be the output for following code?

advertisement
```#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std;
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

void func(char *a, int l, int r)
{
int i;
if (l == r)
cout<<a<<” ,”;
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
func(a, l+1, r);
swap((a+l), (a+i));
}
}
}

int main()
{
char str[] = "AB";
int n = strlen(str);
func(str, 0, n-1);
return 0;
}```

a) AB,BA,
b) BA,AB,
c) AB,BA
d) BA,AB,
View Answer

Answer: a
Explanation: The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. Note that the comma is printed even for the last permutation.

8. What will be the time complexity of the given code?

```#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std;
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

void func(char *a, int l, int r)
{
int i;
if (l == r)
cout<<a<<” ,”;
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
func(a, l+1, r);
swap((a+l), (a+i));
}
}
}

int main()
{
char str[] = "AB";
int n = strlen(str);
func(str, 0, n-1);
return 0;
}```

a) O(n2)
b) O(n * n!)
c) O(n!)
d) O(n log n)
View Answer

Answer: b
Explanation: The recurrence relation for the heap’s algorithm is given by the expression T(n)=n * T(n-1). But as each permutations takes n time to be printed so the overall complexity will be O(n*n!).

9. What will be the output of the following code?

```#include <iostream>
#include<string>
using namespace std;
void func1(string input,string output)
{
if(input.length()==0)
{
cout<<output<<",";
return;
}
for(int i=0;i<=output.length();i++)
func1(input.substr(1),output.substr(0,i) + input[0] + output.substr(i));
}

int main()
{
char str[] = "AB";

func1(str, "");
return 0;
}```

a) AA,BA,
b) AB,BA,
c) BA,AB,
d) AB,AB,
View Answer

Answer: c
Explanation: The given code prints the permutations of the an array. So there will be 2 permutations for an array of 2 elements. In this code the difference is that BA is printed before AB. Note that the comma is printed even for the last permutation.

10. What will be the output of the following code?

```#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std;
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

void func(char *a, int l, int r)
{
int i;
if (l == r)
cout<<a<<” ,”;
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
func(a, l+1, r);
swap((a+l), (a+i));
}
}
}

int main()
{
char str[] = "AA";
int n = strlen(str);
func(str, 0, n-1);
return 0;
}```

a) AA,
b) AA,AA
c) A,A
d) AA,AA,
View Answer

Answer: d
Explanation: The given code prints the permutations of the given array but it is not able to handle duplicates due to which it prints 2P2 permutations even in this case. So the output becomes AA,AA,.

11. What will be the output of the code that generates permutations and also has the ability to handle duplicates, for the input str[]=”AA”?
a) AA
b) AA,AA
c) A,A
d) A
View Answer

Answer: a
Explanation: If a code is able to handle duplicates then the two A’s are not considered to be different elements due to which only one permutation will be formed. So the output will be AA only.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.