Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Have problem in understanding the logic of Integer Partition

Ranch Hand
Posts: 106
2
Hello, Everyone

I have got this problem from my computer teacher that for a number N, is it to be displayed in the form of sums. Like for example 4 can be displayed as [4],[3+1],[2+2],[2+1+1],[1+1+1+1]. I need to write a program to display these partitions for any number N.
I don't have the logic clear and this is the program that I got from Integer Partition Program

I did the dry run of this program in pen and paper and the outputs seem to be correct, but I am not quite following the logic of this program. If some one could help me out in understanding the logic of this problem, it would be very kind of you.

Regards,
Ranajoy

Saloon Keeper
Posts: 8313
148
• 1
Okay, so let's look at the intention of the partition(int n, int max, String prefix) method. It partitions a number n into terms, with each term being no greater than max.

At first we say "partition 4, and I want no term to be greater than 4".

The for-loop then does the following:

Partition 0, with no term being greater than 4, and prefix every solution with " 4":    " 4"
Partition 1, with no term being greater than 3, and prefix every solution with " 3":    " 3 1"
Partition 2, with no term being greater than 2, and prefix every solution with " 2":    " 2 2",    "2 1 1"
Partition 3, with no term being greater than 1, and prefix every solution with " 1":    " 1 1 1 1"

The trick in recursion is to just trace 1 method call, and not to trace deeper recursive calls. Just assume that they "magically work", and see how their calls are combined to achieve what you want.

Ranajoy Saha
Ranch Hand
Posts: 106
2
Okay, but if you can give me a algorithm for solving this problem, so that I could develop my own code, I'd be much happier. I don't like using this code, 'cause I still am not able to understand partition's purpose.

Ranajoy Saha
Ranch Hand
Posts: 106
2
If someone can tell me how to approach to solve this problem recursively , it would be of great pleasure to me.

Stephan van Hulst
Saloon Keeper
Posts: 8313
148
How would you solve this problem without a computer?

If I asked you to write down all sums that total 5, what steps would you take in your mind? Describe it in your own words first. Don't think about code.

Ranajoy Saha
Ranch Hand
Posts: 106
2
By writing all the digits upto in this case 4 and then adding the numbers with prefixes 4,3,2,1

Ranajoy Saha
Ranch Hand
Posts: 106
2
Let the digits be {1,2,3,4} Like 4 == 4 so, 1 combination is 4, then comes 3, so, 4 -3 = 1, 1 exists in my list of elements, so it 3 + 1

Stephan van Hulst
Saloon Keeper
Posts: 8313
148

Ranajoy Saha
Ranch Hand
Posts: 106
2
Let us assume that we are to find the partition of 5. So, let me build an array of numbers from 1 - 5 like arr[] = {1,2,3,4,5}. So, let's begin with n = 5

5 is equal to 5, so print 5 then reduce n by 1 (n--)
4 is not equal to 5, there for sum = 4 + arr[0] = 5, and sum == 5, therefore print 4 + 1,
(n--)
3 is not equal to 5, there for sum = 3 + arr[0] = 4 which is not equal to 5, so, sum += arr[0] which is equal to 5 therefore print 3 + 1 + 1
Again as the parsing of the numbers of the loop is not completed, sum = 3 + arr[1] which is equal to 5 thus print 3 + 2 and as 3 + arr[2] or 3+arr[3] is higher than 5 so, break the loop

This is the way I was thinking of solving this problem. But I wasn't able to create a valid algorithm for progression.

Stephan van Hulst
Saloon Keeper
Posts: 8313
148
You are thinking too much in terms of code. Forget about arrays and loops.

I'm asking you now to write down all partitions of 5. For each partition, explain how you got there. This should not be a lot of work, because there are only 7 decompositions.

Ranajoy Saha
Ranch Hand
Posts: 106
2
Okay, no codes this time.

5 (We began with 5)
4+1 (4 is before 5 and adding 1 to 4 gives 5)
3+2 (3 is before 4 and adding 2 to it gives 5)
3+1+1 (2 can also be written as 1+1)
2+2+1 (2 is before 3 and adding 3 to it gives 5 but as 3+2 already exists breaking 3 to 2+1)
2+1+1+1 (Splitting last 2 to 1+1)
1+1+1+1+1 (Splitting the remaining 2 to 1+1)

I hope you asked for this, if not sorry. This is what I make of "I'm asking you now to write down all partitions of 5. For each partition, explain how you got there."

Stephan van Hulst
Saloon Keeper
Posts: 8313
148
• 1
Excellent!

Now, do you notice a pattern? You saw that getting the decomposition 3 + 1 + 1, was actually the same as applying the partition to 2, in the decomposition 3 + 2.

So you actually performing a partition within a partition? This is recursion!

The pattern here is that for each integer from 5 to 1, you print that integer for each partition of the remainder, right? In pseudocode:

If you understand this pseudocode, and how we got there, then try to realize it as actual Java code.

Don't worry about ignoring decompositions like 1 + 3 + 1 yet, we'll deal with that later.

Ranajoy Saha
Ranch Hand
Posts: 106
2
Thanks for this immense help Stephan. Thank you very much. I don't know about List as of now, so if you could convert it to String, it would help me greatly in understanding. I wish you were my teacher. That'd make my life a lot easier than it is now.

Stephan van Hulst
Saloon Keeper
Posts: 8313
148
• 1