Power Set
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Power Set

  1. #1
    Join Date
    Nov 2005
    Posts
    1

    Smile Power Set

    I need to use a recursive algorithm to find the power set of a given set i.e a set of all the subsets of a given set.
    For example, if a set is {a,b,c}, the power set happens to be a set of {a},{b},{c},{a,b}{a,c},{b,c},{a,b,c}.
    I know that such a thread existed earlier on this forum but the solutions were not very elaborate. There were a lot of codes. Can someone instead give me the algorithm instaed of the source code. It will be of great help to me . I am just beginning to learn recursive algorithms

  2. #2
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: Power Set

    Say, original set contains element a. Then all subsets are divided in 2 classes: ones containing a and ones not. Note that set of sets containing a may be obtaining by adding a to each of sets not containing a. And that's the recursion.
    Code:
    void comb_rec(string a, string pref="")
    {
    	if(!a.empty())
    	{
    		comb_rec(a.substr(1),pref);
    		comb_rec(a.substr(1),pref+a[0]);
    	}
    	else if(!pref.empty())
    		cout<<pref<<endl;
    }
    
    int main()
    {
        comb_rec("abc");
        return 0;
    }
    "Programs must be written for people to read, and only incidentally for machines to execute."

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)