Beginner to Advanced Computing and Logic Building/

...

/

Problem Solving: Union and Intersection of Sets (Using Functions)

Problem Solving: Union and Intersection of Sets (Using Functions)

Learn to create a program that finds the union and intersection of two sets using functions.

We'll cover the following...
Press + to interact
C++
Files
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);
/*
	Assume you have the implementation of the above 4 functions.
*/
void UNION(int A[ ], int sizeA, int B[ ], int sizeB, int UnionSet[ ], int &sizeU)
{
	// Write your code here
}
void intersection(int A[ ], int sizeA,int B[ ], int sizeB,int IntersectionSet[ ],int& iSize)
{
	// Write 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);
    loadSet("B",B, sizeB, rdr);	
	//Sorting the two sets
	//Sorting A	and B
	sort(A, sizeA);
	sort(B, sizeB);
	// Displaying the two sets
	setPrint("A", A, sizeA);
	setPrint("B", B, sizeB);
	// Write your code here.
	// UNION(....);
	// intersection(....);
	return 0;
}

Finding and sorting union of sets

Let’s write a function for computing the union of the two sets,

void UNION(int A[ ], int sizeA, int B[ ], int sizeB, int UnionSet[ ], int &sizeU)

In the UNION function, we have the following six parameters:

  • The first parameter is set A[].
  • The second parameter is set sizeA.
  • The third parameter is set B.
  • The fourth parameter is set sizeB.
  • The fifth parameter is UnionSet[], which stores the union of both sets.
  • The last parameter is the size of the union, sizeU, which is passed by reference.

This function will store the elements of set A in UnionSet[]. It will then check each element of set B in the set A to see whether these elements are present in set A or not, using the isPresent() function. If an element is not present in set A, it’ll simply append that element into UnionSet[].

After insertion of all the elements of A and B, we will simply sort it by calling sort(UnionSet,sizeU). This will give us a sorted array.

Let us look at the two implementations, namely with and without functions.

Finding union and intersection (with and without functions)

Previous implementation of computing union

int UnionSet[500] = { 0 };
for (int ai = 0; ai <= sizeA - 1; ai++)
{
	UnionSet[ai] = A[ai]; // Add all the elements in A in the unionSet
}
int check = 0, ui = sizeA;
for (int bi=0; bi<=sizeB-1; bi++)
{
  check = 0;
  for (int ai=0; ai<=sizeA-1; ai++)
  {
   if(B[bi] == A[ai]) 
   { // B[bi] is already in A
     check++; 
     break;
   }
  }
  if (check == 0) 
  {    // B[bi] is a new element
   UnionSet[ui] = B[bi];
   ui++;
  }
}
int uSize = UI; 
   // Size of union set store in uSize

// Now Sorting Union set
for (int t = 1; t <= uSize-1; t++)
{
 for(int ui = 0; ui +1< uSize; ui++)
 {
  if (UnionSet[ui] > UnionSet[ui+1])
    swap(UnionSet[ui], UnionSet[ui+1]);
 }
}

Union set function

void UNION(int A[ ], int sizeA, int B[ ], 
  int sizeB, int UnionSet[ ], int &sizeU) 
{
  for (int ai=0; ai<=sizeA-1; ai++)
  {
    UnionSet[ai] = A[ai];
               
// Add all the elements in unionSet
  }
  int check = 0, ui = sizeA;
  for (int bi=0; bi<= sizeB-1; bi++)
  {
   if(!isPresent(UnionSet,ui,B[bi]))
   {// if B[bi] is not in UnionSet
     UnionSet[ui] = B[bi];             
     ui++;
   }
  }
  sizeU = ui;
    //Sorting Union-Set
  sort(UnionSet, sizeU);

}
int main()
{
.
.
.
 int UnionSet[500] = { 0 },uSize;
 UNION(A, sizeA, B, sizeB,UnionSet, uSize);
 printArray("AUB",UnionSet,uSize);
.
.
.
}

Instruction: Add the function UNION() and test it in the main().

Note that union is also a keyword (a reserved word by C++, just like int, char, long, etc.). That is why we have used all capital letters (UNION()) to name our function.

Intersection of sets

Let’s make the function:

Press + to interact
void intersection(int A[ ], int sizeA,int B[ ], int sizeB,
                                                    int IntersectionSet[ ],int& iSize);

In the intersection function, we have the following six parameters:

  • The first parameter is set A[].
  • The second parameter is set sizeA.
  • The third parameter is set B.
  • The fourth parameter is set sizeB.
  • The fifth parameter is IntersectionSet[], which stores the common elements of both sets.
  • The last parameter is the size of the intersection set iSize.

This function will call the isPresent() function for checking if an element is present in both sets A and B and simply store them in intersectionSet[].

Intersection set algorithm

int IntersectionSet[500] = { 0 };
int ii = 0;
for (int bi = 0; bi <= sizeB - 1; bi++)
{
	for (int ai = 0; ai <= sizeA - 1; ai++)
	{
		if (B[bi] == A[ai])
			check++;
	}
	if (check != 0)
	{
		IntersectionSet[ii] = B[bi];
		ii++;
	}
	check = 0;
}

Intersection set function

void intersection(int A[ ], int sizeA, 
               int B[ ], int sizeB, 
      int IntersectionSet[ ],int& iSize)
{
    int ii = 0;
    int check;
    for (int bi = 0; bi <= sizeB - 1; bi++)
    {
        if(isPresent(A, sizeA, B[bi]))
        {
            IntersectionSet[ii] = B[bi];
            ii++;
        }
        check = 0;
    }
    iSize = ii;
}

Instruction: Add the intersection() function in the playground above and test it inside main(). Don't forget to display the result of the intersection on the console.

Ask