Program Code

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

/**
 * Generates the power set of a given set.
 * 
 * @param set A vector containing the elements of the set.
 * @return A vector of vectors containing all subsets (the power set).
 */
vector<vector<int>> generatePowerSet(const vector<int> &set) {
    vector<vector<int>> powerSet;
    int setSize = set.size();
    int powerSetSize = 1 << setSize; // 2^n subsets

    // Generate each subset
    for (int i = 0; i < powerSetSize; ++i) {
        vector<int> subset;
        for (int j = 0; j < setSize; ++j) {
            // Check if jth element is included in the subset
            if (i & (1 << j)) {
                subset.push_back(set[j]);
            }
        }
        powerSet.push_back(subset);
    }
    return powerSet;
}

/**
 * Prints the power set.
 * 
 * @param powerSet A vector of vectors representing the power set.
 */
void printPowerSet(const vector<vector<int>> &powerSet) {
    cout << "{\n";
    for (const auto &subset : powerSet) {
        cout << "  { ";
        for (const int &elem : subset) {
            cout << elem << " ";
        }
        cout << "}\n";
    }
    cout << "}\n";
}

int main() {
    vector<int> inputSet = {1, 2, 3}; // Example set
    vector<vector<int>> powerSet = generatePowerSet(inputSet);
    printPowerSet(powerSet);
    return 0;
}

Program Explanation

This program generates the power set of a given set using bit manipulation.

Structure of the Program:

• Includes: The program includes standard libraries such as iostream for input and output, vector for dynamic arrays, and algorithm for various utility functions.
• generatePowerSet Function:
  • Parameters: Takes a vector of integers representing the input set.
  • Returns: A vector of vectors, where each vector represents a subset of the input set.
  • Logic: The total number of subsets (2^n) is determined using bitwise shifting. Each subset is generated by checking each bit of an integer (from 0 to 2^n – 1) to decide whether to include each element from the original set.
• printPowerSet Function:
  • Parameters: Takes the generated power set as input.
  • Functionality: Iterates through each subset in the power set and prints it in a readable format.
• main Function:
  • Initializes an example set (in this case, {1, 2, 3}).
  • Calls generatePowerSet to create the power set and printPowerSet to display it.

Conclusion

This program effectively demonstrates how to generate the power set of a given set using C++. The use of bit manipulation makes it efficient for smaller sets.