Jump to content
  • Advertisement
Sign in to follow this  
Kommi10

what is the name of this problem (if it exists)

This topic is 4770 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

Ok lets say I have a the number 5, and I wish to generate all possible combinations of addition. What I mean is this: 5,0 4,1 3,1,1 3,2 2,1,1,1 2,2,1 1,1,1,1,1 if you add the numbers up in each combo they all = 5. Is there a name for this time of problem / algorithm?

Share this post


Link to post
Share on other sites
Advertisement
A trivial recursion should do it.

Quote:
Is there a name for this time of problem / algorithm?


I believe it would be a decomposition (but not into prime factors) or possibly something called "homework" [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
A trivial recursion should do it.


Not that trivial, mind you. Well, unless you don't mind repeating yourself, otherwise you have to modify the problem a little bit before it becomes recursive. That, or you can use trivial recursion and a hash table :p

Also, is you icon a veterinary glove? [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Not that trivial, mind you. Well, unless you don't mind repeating yourself, otherwise you have to modify the problem a little bit before it becomes recursive. That, or you can use trivial recursion and a hash table :p


The constraint that your numbers must be monotonously decreasing should be enough to guarantee unicity.

Quote:
Also, is you icon a veterinary glove? [grin]


Ask kSquared. [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
The constraint that your numbers must be monotonously decreasing should be enough to guarantee unicity.


At which point you're solving the problem "return all monotonously decreasing sequences of numbers smaller than X which add up to Y" recursively instead. Which isn't trivial anymore.

Share this post


Link to post
Share on other sites
I would try looking for stuff on the 'partition function P' as it is the function in combinatorics that returns the number of ways a positive integer N can be written as the sum of positive integers. Obviously 0 is missing but it's the same idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by O_o
I would try looking for stuff on the 'partition function P' as it is the function in combinatorics that returns the number of ways a positive integer N can be written as the sum of positive integers. Obviously 0 is missing but it's the same idea.


Great, thanks a lot for that one.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Which isn't trivial anymore.


All it changes is the number your counting down from at each level of recursion. And yes, I'm still calling it trivial.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVykAt which point you're solving the problem "return all monotonously decreasing sequences of numbers smaller than X which add up to Y" recursively instead. Which isn't trivial anymore.


The definition of "trivial" is, of course, varying.

I would go with Fruny on this one. You need to pass along one or two extra pieces of state, but it's not rocket science. The recursion condition is "return all decreasing sequences of numbers adding up to X, where the first number is no greater than Y".

Coding and debugging that should take less than 10 minutes.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!