Thread: How to print out all possible subsets using set.h?

  1. #1
    Registered User
    Join Date
    Jan 2014
    Location
    Hawaii
    Posts
    6

    Question How to print out all possible subsets using set.h?

    Hello Everyone,
    I have the following problem that I can't solve and would appreciate the help. so the problem is the following.

    Write a function that takes a set of distinct Strings as input and prints out all possible subsets.
    For example, given input S=("Alice", "Bob", "Dave"), the function should output
    (),
    ("Alice"),
    ("Bob"),
    ("Alice","Bob"),
    ("Dave"),
    ("Alice", "Dave" ),
    ("Bob", "Dave" )
    ("Alice", "Bob", "Dave")


    Note that your function may display the subsets in order different from the above. For
    simplicity, assume that the size of the set is no larger than 32

    Code:
    #include<iostream>
    #include<string>
    #include<set>
    using namespace std;
    void DisplayAllSubsets(set<string> S)
    my attempt of the

    Code:
    void DisplayAllSubsets(set<string> S){  set<string>::iterator it; 
     int count = 0; // may need it for finding the amount of combination
     for ( it = S.begin(); it != S.end(); ++it)
        { // Not sure how to proceed 
        }
    }
    I have no idea how I could use the set.h tools to output the combination shown in the problem. Any ideas, suggestion, or another container such as vectors that is implemented for this problem would be helpful.

    Thank you for your time

  2. #2
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Have a look at the standard header <algorithm>. While there is nothing there that would do what you need directly there are functions there that could be used. You might need to use some other container type (like vector) that can be reordered by the algorithms.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  3. #3
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    928
    I'd use the fact that there's an isomorphism between the power set of a set size N and the binary strings of length N.
    Code:
    Original set: { a, b, c }
    
    000 = "a is not in the subset, b is not in the subset, c is not in the subset" = { }
    001 = "a is not in the subset, b is not in the subset, c is in the subset" = { c }
    ...
    101 = "a is in the subset, b is not in the subset, c is in the subset" = { a, c }
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find all subsets with sum of x
    By mgracecar in forum C Programming
    Replies: 1
    Last Post: 10-20-2013, 02:43 PM
  2. How to do array subsets?
    By gormster in forum C Programming
    Replies: 5
    Last Post: 11-14-2007, 06:50 AM
  3. Subsets of binary string
    By damonbrinkley in forum C Programming
    Replies: 4
    Last Post: 05-03-2005, 09:00 AM
  4. compute the subsets of a set
    By k_w_s_t_a_s in forum C Programming
    Replies: 4
    Last Post: 06-01-2003, 05:54 PM
  5. subsets
    By scottmanc in forum C++ Programming
    Replies: 7
    Last Post: 03-11-2003, 08:22 AM