Problem Solving: Subset of Sets (Using Functions)

Learn to create a program that determines whether a set is a subset of another set using functions.

We'll cover the following

This lesson will guide you through how the two implementations (with and without functions) for finding subsets differ.

Instruction: Use the following playground to write the complete code for all the upcoming tasks in this lesson.

We’ve already added code for the loading, sorting, and displaying sets, so you can use that directly wherever needed.

Press + to interact
main.cpp
Sets.txt
#include <iostream>
#include <fstream>
using namespace std;
void loadSet(const char Msg[], int S[], int &size, ifstream &rdr);
void sort(int S[ ], int size);
void setPrint(const char Msg[], int S[], int size);
bool isPresent(int S[], int size, int t)
{
	// Add your code here. 
}
bool isSubset(int subSet[],	int sizeSubSet,
	int supSet[], int sizeSupSet)
{
	// Add your code here. 
}
void subsetTest(int A[], int sizeA,
	int B[], int sizeB)
{
	// Add your code here. 
}
int main()
{
	const int capacity = 500;
	int A[capacity] = { 0
	}, B[capacity] = { 0
	}, sizeA, sizeB;
	ifstream rdr("Sets.txt");
	loadSet("A", A, sizeA, rdr);	// load sizeA many entries
	loadSet("B", B, sizeB, rdr);	// load sizeB many entries
	sort(A, sizeA);  // Sorting A 
	sort(B, sizeB);  // Sorting B
	setPrint("A", A, sizeA);
	setPrint("B", B, sizeB);
	/* Add the function call to find whether A
	   is a Subset of B or B is a subset of A or none.
	*/
}

Finding A⊆BA \subseteq B or B⊆AB \subseteq A

Before we write a subset finding function, we can see that finding a value in an array is a kind of subproblem that we will be looking for in each iteration of subset finding. Why not make it a separate function?

Utility function: bool isPresent(int S[],int size,int t)

We need to check whether a specific element is in the other set or not, and based on that we need to decide on whether a specific element should be added to the solution set or not.

Press + to interact
bool isPresent(int S[ ], int size, int t)
{
  for(int si=0; si<size; si++)
  {
     if(S[si]==t)
        return true;
  }
  return false;
}

Instruction: Add the function, bool isPresent(int S[ ], int size, int t), in the playground and test it by calling this function on a certain number to search inside the array.

Here’s the sample code you may use inside main for testing:

Press + to interact
int main()
{
.
.
.
    cout << isPresent(A, sizeA, 3);   // it should print 1
    cout << isPresent(A, sizeA, 11);  // it should print 0
    // Write the testing for searching in B by your own
.
.
.
}

Exercise: Modify the isPresent() function, which should be a little more efficient than the given implementation.

Hint: Use the information that the passed array is sorted.

Subset of sets

Let’s have the implementations of subset reporting by making two functions.

The signature of the first function is as follows:

bool isSubset(int subSet[ ], int sizeSubSet, int supSet[ ], int sizeSupSet)

We have the following four parameters:

  • subSet[]: This is a set.
  • sizeSubSet: This is the size of the first set.
  • supSet[]: This is the second set.
  • sizeSupSet: This is the size of the second set.

Instead of a nested loop now, we’ll iterate through each element—subSet[ai] in subSet—and check its presence by calling the isPresent(supSet, sizeSupSet, subSet[ai]) function. If it is not present, the function must immediately return false. In the case of element subSet[ai] presence in supSet, it should keep iterating because we need to check for all the values of subSet to be inside supSet. Therefore, After the loop, it should return true.

Note: In the isSubset() function, we are only testing whether the first set is the subset of the second.

The second function is as follows:

void subsetTest(int A[ ], int sizeA, int B[ ], int sizeB)

The subsetTest() function will check the size of both sets and call the isSubset() function based on the size—whether set A is a subset of B or set B is a subset of A.

Look at the implementations below without and with functions.

Previous implementation of checking A⊆BA \subseteq B

int count =0;
if (sizeA <= sizeB)
{
  for(int ai = 0; ai<=sizeA-1; ai++)
  {
    for(int bi = 0; bi<=sizeB-1; bi++)
    { // checking for A[ai] is in B
      if(A[ai] == B[bi])   
      { // Remember A[ai] is in B
        count++;          
        break;            
        // No need to check any further
      }
    }
  }
if (count == sizeA)
 cout << "\nA is a subset of B.\n";
else
 cout << "\nNeither is a subset \n";
}

Checking for B⊆AB \subseteq A

else if (sizeA > sizeB)
{
  for(int bi = 0; bi <= sizeB - 1; bi++)
  {
    for(int ai = 0; ai<= sizeA-1; ai++)
    {
      if (B[bi] == A[ai])
      {  count++;
         break;
      }
   }
if (count == sizeB)
  cout << "\nB is a subset of A.\n";
else
  cout << "\n Neither is a subset\n";
}

Checking for set A⊆BA \subseteq B

bool isSubset(int subSet[ ],
          int sizeSubSet, 
          int supSet[ ], int sizeSupSet)
{
 for (int ai = 0; ai<=sizeSubSet- 1;ai++)
 {

if( !isPresent(supSet, sizeSupSet, subSet[ai]))
       return false; 
    // remember that subSet[ai] is present
  }
  return true;
}

Checking for set A⊆BA \subseteq B or B⊆AB \subseteq A

void subsetTest(int A[ ], int sizeA, 
                   int B[ ], int sizeB)
{
  int count =0;
  if (sizeA <= sizeB)
  { // checking A is subset of B
     if(isSubset(A,sizeA,B,sizeB))
      cout << "\nA is a subset of B.\n";
     else
      cout << "\n Neither is a subset \n";
  }
  else if (sizeA > sizeB)
  {  // checking B is subset of A        
    if(isSubset(B,sizeB,A,sizeA))
      cout << "\nB is a subset of A.\n";
    else
      cout << "\n Neither is a subset \n";
  }
}

Calling subsetTest() function in main():

int main()
{
.
.
.
   subsetTest(A, sizeA, B, sizeB);
.
.
.
}

Instruction: Add the functions isPresent(), isSubset(), and subsetTest(). Test them inside main(), and see the output.

Complete implementation

Look at the code below to see the complete implementation:

Press + to interact
main.cpp
Sets.txt
#include <iostream>
#include <fstream>
using namespace std;
void sort(int S[ ], int size);
void loadSet(const char Msg[], int S[], int &size, ifstream &rdr);
void setPrint(const char Msg[], int S[], int size);
bool isPresent(int S[], int size, int t)
{
	for (int si = 0; si < size; si++)
	{
		if (S[si] == t)
			return true;
	}
	return false;
}
bool isSubset(int subSet[],	int sizeSubSet,
	int supSet[], int sizeSupSet)
{
	for (int ai = 0; ai <= sizeSubSet - 1; ai++)
	{
		if (!isPresent(supSet, sizeSupSet, subSet[ai]))
			return false;
		// remember that subSet[ai] is present
	}
	return true;
}
void subsetTest(int A[], int sizeA,	int B[], int sizeB)
{
	int count = 0;
	if (sizeA <= sizeB)
	{
		// checking A is subset of B
		if (isSubset(A, sizeA, B, sizeB))
			cout << "\nA is a subset of B.\n";
		else
			cout << "\n Neither is a subset \n";
	}
	else if (sizeA > sizeB)
	{
		// checking B is subset of A        
		if (isSubset(B, sizeB, A, sizeA))
			cout << "\nB is a subset of A.\n";
		else
			cout << "\n Neither is a subset \n";
	}
}
int main()
{
	const int capacity = 500;
	int A[capacity] = { 0
	}, B[capacity] = { 0
	}, sizeA, sizeB;
	ifstream rdr("Sets.txt");
	loadSet("A", A, sizeA, rdr);	// load sizeA many entries
	loadSet("B", B, sizeB, rdr);	// load sizeB many entries
	sort(A, sizeA);  // Sorting A 
	sort(B, sizeB);  // Sorting B
	setPrint("A", A, sizeA);
	setPrint("B", B, sizeB);
	// For testing B is a subset of A
	subsetTest(A, sizeA, B, sizeB);
}