Question

Q2. Answer the following questions assignment, you will develop a well-documented pseudocode that generates all possible subsets of a given set T (i.e. power set of T) containing n elements with the following requirements: your solution must be non-recursive, and must use a stack and a queue to solve the problem. For example: ifT- {2, 4, 7,9; then your algorithm would generate: U, t2), (4;, {7), {9;, 12,4), 12,7;, 12.9;, 14,7), 14,9), 17,9;, ...etc. (Note: your algorithm's output need not be in this order). b) Calculate the time complexity of your algorithm using the big-Oh notation. Show all calculations

Answer 1

Approach Used:

Iterate from 0 to the size of the power set.

For each index check at what all positions the bit 1 is set.

Take the values from the Input set at those positions in the index where the 1 is set and insert into the stack.

At the end insert the set into the queue.

#include <iostream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int main()
{
   vector<int> inputSet({ 2,4,7,9 });
   queue<stack<int>> myPowerSet;

   int nlenght = inputSet.size();

   for (size_t i = 0; i < pow(nlenght,2); i++)
   {
       int cnt = 0;
       stack<int> set;
       while (cnt < 4)
       {
           if (i & (1 << cnt))
               set.push(inputSet[cnt]);
           cnt++;
       }
       myPowerSet.push(set);
   }

   return 0;

}

Here myPowerSet contains all the subsets of the input set.

The time complexity of this solution will be 4 * n* n where n is the length of the input Set.