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

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

## 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 on other sites
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 on other sites
Quote:
 Original post by FrunyA 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 on other sites
homework it is not. Thanks I will give a recursive solution a try

##### Share on other sites
Quote:
 Original post by ToohrVykNot 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]

##### Share on other sites
Quote:
 Original post by FrunyThe 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 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 on other sites
Quote:
 Original post by O_oI 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 on other sites
Quote:
 Original post by ToohrVykWhich 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 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.

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5

• 10
• 27
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633405
• Total Posts
3011681
• ### Who's Online (See full list)

There are no registered users currently online

×