CSCI 3342 Submission 07
Generating and Displaying Power Sets

Overview

This week you will have a chance to showcase your "recursion chops" by writing a recursive function to compute the power set of a set of integers or characters, which will also require you to make critical use of the STL set container. You can solve the problem for this submission however you like, but I strongly suggest that you write two functions, a recursive one to compute the power set of a set of integers or characters provided as input, and a non-recursive function that takes as input that power set and displays each set of the power set in the required output format.

The power set of any set is the set of all subsets of that set. One can prove (using mathematical induction, and perhaps other techniques as well) that the number of sets in the power set of a finite set containing n elements is 2^n (2 to the power n). So, for example, the power set of any set containing 3 elements will contain 8 elements. If this is a new concept for you, construct a set of three elements and then write down all of its subsets to confirm the previous statement.

Steps to Perform

1. Copy the demo executable and run the program a few times, first with no input to study the program info, then a few times with different integer and character input in the valid ranges to see the kind of output you get, and how that output is formatted.
2. Design the functions you will need for a solution to this problem, and write the necessary pseudocode for them.
3. Revise your solution until you are convinced that the functions that implement your pseudocode will be the ones you want.
4. Translate your pseudocode into C++ code and continue testing your program until you are convinced it works correctly.
5. When you are finished, make sure your source code file is identified, formatted, and documented properly.
6. Finally, submit the required files to the appropriate directory.

Additional Notes, Requirements, Specifications and/or Hints (if any)

1. Note that although the demo (and your program) require the user to keep the power set small to limit the amount of output, your functions that compute the power set and should still work fine, whatever the size of the set. It's just that the output is not likely to be very pretty if you have too much of it. Since there is no error checking, the user is expected to enter an integer from 1 to 6 (inclusive) or a lowercase letter from a to f (inclusive), or the program is not responsible for what happens next.
2. Here is some "recursive pseudocode" that you may find helpful when writing your recursive routine to build the power set of a set:

   if (the set is empty)
       return the empty set
   else
       Take an element out of the set and then:
       (1) Find the power set of the "reduced" set
       (2) Add the removed element to each set in the power set of that reduced set
       return the "union" of the two sets in (1) and (2) above
   

3. Note that no program information file is provided this time, so this is another opportunity to make use of a single C++ "raw string" to contain the text for display.