-
November 8th, 2005, 02:28 PM
#1
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
-
November 11th, 2005, 07:42 PM
#2
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|