Data Structures & Algorithms Multiple Choice Questions on “Generating Combinations”.
1. What is meant by the term lexicographical order?
a) dictionary ordering of elements
b) reverse dictionary ordering of elements
c) to sort according to value of first element
d) to sort according to value of last element
Answer: a
Clarification: 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 combinations of 2 elements will be formed from the array arr={1,2,3}?
a) 1
b) 2
c) 3
d) 4
Answer: c
Clarification: No.of combinations of r elements for an array of size n will be given by the formula nCr. So for the given problem, we have 3C2=3.
3. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?
a) {{2,1},{3,2},{3,1}}
b) {{1,2},{2,3},{1,3}}
c) {{1,2},{1,3},{2,3}}
d) {{2,1},{3,1},{3,2}}
Answer: c
Clarification: The number of combinations for the problem will be 3 according to the formula 3C2. When ordered in lexicographical manner these will be {{1,2},{1,3},{2,3}}.
4. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from array of size n?
a) O(n*r)
b) O(n/r)
c) O(n)
d) O(r)
Answer: d
Clarification: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. This memory is required by an array that is used for storing combinations formed.
5. The code for printing combinations is in-place.
a) true
b) false
Answer: b
Clarification: Code to print combinations will require an auxiliary space of O(r) other than call stack memory. So it is not an in-place algorithm.
6. What will be the time complexity of the code to print combinations?
a) O(n)
b) O(n2)
c) O(n log n)
d) O(2n)
Answer: d
Clarification: The recurrence relation of the code to print combinations will be T(n)=2T(n-1)+k. It is found to be equal to O(2n).
7. What will be the output for the following code?
#include
void combination(int arr[],int n,int r,int index,int aux[],int i);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, n, r, 0, aux, 0);
}
void combination(int arr[], int n, int r, int index, int aux[], int i)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",aux[j]);
printf(", ");
return;
}
if (i >= n)
return;
aux[index] = arr[i];
combination(arr, n, r, index+1, aux, i+1);
combination(arr, n, r, index, aux, i+1);
}
int main()
{
int arr[] = {1, 2,2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
return 0;
}
a) 1 2, 1 2, 2 2
b) 1 2, 1 2, 2 2 ,
c) 1 2, 2 1, 2 2 ,
d) 1 2, 2 1, 2 2
Answer: b
Clarification: The given code prints the combinations of the given array in lexicographical order.The given code considers the duplicate 2s as different entities.Note that the comma is printed even for the last combination.
8. Which of the following code prints the combinations of a given array?
a)
#include
void combination(int arr[], int aux[], int start, int end, int index, int r);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end,
int index, int r)
{
if (index <= r)
{
for (int j=0; j<r; j++)
printf("%d ", aux[j]);
printf(", ");
return;
}
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
}
}
int main()
{
int arr[] = {1, 2, 3};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
b)
#include
void combination(int arr[], int aux[], int start, int end,
int index, int r);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end,
int index, int r)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ", aux[j]);
printf(", ");
return;
}
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
}
}
int main()
{
int arr[] = {1, 2, 3};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
c)
#include
void combination(int arr[], int aux[], int start, int end,
int index, int r);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end,
int index, int r)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ", aux[j]);
printf(", ");
return;
}
for (int i=start; i<=end ; i++)
{
aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
}
}
int main()
{
int arr[] = {1, 2, 3};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
d)
#include
void combination(int arr[], int aux[], int start, int end,
int index, int r);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end,
int index, int r)
{
if (index <= r)
{
for (int j=0; j<r; j++)
printf("%d ", aux[j]);
printf(", ");
return;
}
for (int i=start; i<=end; i++)
{
aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
}
}
int main()
{
int arr[] = {1, 2, 3};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
Answer: b
Clarification: In the code we start from first index (index = 0) in array aux and one by one fix elements at this index and recur for remaining indexes. Finally, when index becomes equal to r we print the combination.
9. Which of the following code prints the combinations of a given array?
a)
#include
void combination(int arr[],int n,int r,int index,int aux[],int i);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, n, r, 0, aux, 0);
}
void combination(int arr[], int n, int r, int index, int aux[], int i)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",aux[j]);
printf(", ");
return;
}
if (i >= n)
return;
aux[index] = arr[i];
combination(arr, n, r, index+1, aux, i+1);
combination(arr, n, r, index, aux, i+1);
}
int main()
{
int arr[] = {1, 2,2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
return 0;
}
b)
#include
void combination(int arr[],int n,int r,int index,int aux[],int i);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, n, r, 0, aux, 0);
}
void combination(int arr[], int n, int r, int index, int aux[], int i)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",aux[j]);
printf(", ");
return;
}
if (i >= n)
return;
aux[index] = arr[i];
combination(arr, n, r, index+1, aux, i+1);
combination(arr, n, r, index+1, aux, i+1);
}
int main()
{
int arr[] = {1, 2,2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
return 0;
}
c)
#include
void combination(int arr[],int n,int r,int index,int aux[],int i);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, n, r, 0, aux, 0);
}
void combination(int arr[], int n, int r, int index, int aux[], int i)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",aux[j]);
printf(", ");
return;
}
if (i >= n)
return;
aux[index] = arr[i];
combination(arr, n, r, index-1, aux, i+1);
combination(arr, n, r, index, aux, i+1);
}
int main()
{
int arr[] = {1, 2,2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
return 0;
}
d)
#include
void combination(int arr[],int n,int r,int index,int aux[],int i);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, n, r, 0, aux, 0);
}
void combination(int arr[], int n, int r, int index, int aux[], int i)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",aux[j]);
printf(", ");
return;
}
if (i >= n)
return;
aux[index] = arr[i];
combination(arr, n, r, index, aux, i+1);
combination(arr, n, r, index+1, aux, i+1);
}
int main()
{
int arr[] = {1, 2,2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
return 0;
}
Answer: a
Clarification: In this method we consider each method one by one and recur for two cases.In first case we include that element in our array and in second case we don’t .When the number of elements in the array aux[] becomes equal to r then we print that combination.
10. What will be the output for the following code?
#include
void combination(int arr[], int aux[], int start, int end, int index, int r);
void print(int arr[], int n, int r)
{
int aux[r];
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end, int index, int r)
{
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ", aux[j]);
printf(", ");
return;
}
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{ aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
}
}
int main()
{
int arr[] = {1, 2, 3};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
a) 1 2, 1 3, 2 3
b) 1 3,1 2,2 3,
c) 1 2, 1 3, 2 3,
d) 1 2,1 3,2 3,
Answer: c
Clarification: The given code prints the combinations of the given array in lexicographical order.Note that the comma is printed even for the last combination.
11. What will be the output for the following code?
#include
#include
void combination(int arr[], int aux[], int start, int end, int index, int r);
int compare (const void * a, const void * b)
{ return ( *(int*)a - *(int*)b ); }
void print(int arr[], int n, int r)
{
int aux[r];
qsort (arr, n, sizeof(int), compare);
combination(arr, aux, 0, n-1, 0, r);
}
void combination(int arr[], int aux[], int start, int end, int index, int r)
{
if (index == r)
{
for (int i=0; i<r; i++)
printf("%d " ,aux[i]);
printf(", ");
return;
}
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
aux[index] = arr[i];
combination(arr, aux, i+1, end, index+1, r);
while (arr[i] == arr[i+1])
i++;
}
}
int main()
{
int arr[] = {1, 2, 2};
int r = 2;
int n = sizeof(arr)/sizeof(arr[0]);
print(arr, n, r);
}
a) 1 2, 1 2,2 2,
b) 1 2, 2 1, 2 2,
c) 1 2, 2 2,
d) 1 2, 2 2, 2 1,
Answer: c
Clarification:The given code prints combination of the elements of a given array.But the difference here is that this code also handles duplicate elements due to which we get only 2 combinations instead of 3.
& Algorithms.
and Answers.