Jump to content
  • Advertisement
Sign in to follow this  
barakat

DOing IT Recursively !!

This topic is 5111 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How to get the subsets of a given set (array) recursively ?? Pick one element - call it n. Take all of the subsets of your set minus {n} (note: this is the recursive call). Add on another copy of each of those subsets but include {n} in each of them. For example, if you start with {1,2,3} Pick a number, such as 3. Take all subsets of {1,2} this gives you {}, {1}, {2}, {1,2}. Also include 3 in each of those sets: this gives you {3}, {1,3}, {2,3}, {1,2,3}. but i cant write this into direct code that can help me to say that if i was given a list {3,3,6,13} then { 3 , 3 , 13 } = 19 and { 6 ,13 } = 19 ??

Share this post


Link to post
Share on other sites
Advertisement
Hmm, I understood your post until this part:
Quote:

then { 3 , 3 , 13 } = 19
and { 6 ,13 } = 19

How does {3, 3, 13} equal 19? Are you suppossed to get the sum of every subset too?

Anyway this is homework so I'm just going to give you pointers.

For one thing, you are going to need to have some data structure that keeps track of lists of sets. Maybe a std::vector of sets, or you can write your own container. What language are you using, anyway? Also, you'll have to decide how you want to store individual sets. They can be std::vectors too. Or, I think there is some sort of "set" container in the STL. Or you could write your own.

Whatever containers you use, you'll need to write code that can iterate through a list of sets. You'll also need a way to append one list of sets onto another list. And you'll ALSO need a function that removes duplicates from a list of sets, because you'll end up with some duplicates when you append lists.

Once you get those building blocks together, the actual problem is pretty simple.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!