• Post Reply Bookmark Topic Watch Topic
  • New Topic

Integer Partition using recursion  RSS feed

 
Carmine Gendry
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I'm given this problem:
- Implement a program in Java to generate all of the unique positive partitions of a positive integer. Your program should print only those partitions containing at least one addend equal 1 (one).

Example with input 4:


I have found several solutions online that don't include checking for those solutions that include at least one addend equal to 1 and that is fine. My difficulty is trying to understand what exactly is going on within the algorithm to come up with the result.
This is the solutions I'm looking at:


I have gone through it by hand and get this result after the for-loop:


However, how does this result in this being displayed:

Also, after this how would I make sure that the results that don't include '1' aren't printed?


Any help will be greatly appreciated!
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's actually pretty easy. All partitions of 4 that contain at least one 1 is the same as all partitions of 3, except you add 1.
 
Carmine Gendry
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Stephan van Hulst wrote:That's actually pretty easy. All partitions of 4 that contain at least one 1 is the same as all partitions of 3, except you add 1.

I'm afraid I don't understand.
I apologize in advance.
 
Tobias Bachert
Ranch Hand
Posts: 85
18
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Regarding the output:
Your approach is correct, you have to repeat the method for each of the four statements you got until the recursion ends (-> when n==0 is):
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You've already written down the expected output for input 4. Now write down what the current program outputs for input 3. Notice anything?
 
Carmine Gendry
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tobias Bachert wrote:Regarding the output:
Your approach is correct, you have to repeat the method for each of the four statements you got until the recursion ends (-> when n==0 is):

I can't believe I missed that. It makes so much more sense now.
Thank you so much!

Stephan van Hulst wrote:You've already written down the expected output for input 4. Now write down what the current program outputs for input 3. Notice anything?

Output for input 3:


It's just one 1 added to each line of output.
So would it be finding the integer partition of n-1 to begin with and add 1 to the end of the output?
 
Stephan van Hulst
Saloon Keeper
Posts: 7817
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carmine Gendry wrote:So would it be finding the integer partition of n-1 to begin with and add 1 to the end of the output?

Yep! Welcome to CodeRanch, by the way.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!