Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Integer Partition using recursion

 
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!
 
Saloon Keeper
Posts: 12129
258
  • 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.
 
Ranch Hand
Posts: 86
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: 12129
258
  • 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: 12129
258
  • 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.
 
I've been selected to go to the moon! All thanks to this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic