The power set of a given set is the set of all possible subsets, including the empty set and the set itself. For example, the power set of {1, 2} is { {}, {1}, {2}, {1, 2} }.

Python Program to Generate the Power Set

def power_set(original_set):
    """
    Generate the power set of a given set.

    :param original_set: A set of elements.
    :return: A list containing all subsets of the original set.
    """
    # Convert the original set to a list for indexing
    elements = list(original_set)
    n = len(elements)
    # Total number of subsets = 2^n
    total_subsets = 1 << n  # Equivalent to 2 ** n

    # Initialize the power set
    power_set_result = []

    # Iterate through all possible combinations
    for i in range(total_subsets):
        subset = []
        for j in range(n):
            # Check if jth element should be included
            if (i & (1 << j)) > 0:
                subset.append(elements[j])
        power_set_result.append(subset)

    return power_set_result

# Example usage
if __name__ == "__main__":
    my_set = {1, 2, 3}
    result = power_set(my_set)
    print("Power Set:")
    print(result)
    

Explanation of the Program Structure

1. Function Definition

The function power_set is defined to take one argument: original_set, which is the input set for which we want to generate the power set.

2. Convert Set to List

Inside the function, the input set is converted to a list called elements to facilitate indexing. The length of the list is stored in the variable n.

3. Calculate Total Subsets

The total number of subsets is calculated using the expression 1 << n, which is equivalent to 2 ** n. This bitwise operation efficiently computes 2^n.

4. Initialize Power Set

An empty list power_set_result is initialized to store all subsets generated during the iterations.

5. Iterating Through Combinations

A loop iterates through all possible combinations from 0 to total_subsets - 1. Each integer i represents a combination of elements, where each bit in the binary representation of i indicates whether to include an element.

6. Building Subsets

For each combination, another loop checks each element’s index j. If the jth bit of i is set (i.e., (i & (1 << j)) > 0), the corresponding element is added to the current subset.

7. Storing the Result

After constructing a subset, it is appended to the power_set_result list.

8. Returning the Result

Once all combinations have been processed, the complete power set is returned as a list of subsets.

Example Usage

The program includes an example usage of the power_set function, where a set {1, 2, 3} is defined, and the power set is computed and printed.

Conclusion

This program provides a straightforward approach to generating the power set of any given set using bitwise operations in Python. It effectively demonstrates the concept of combinations and the use of binary representation in subset generation.