Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Have problem in understanding the logic of Integer Partition  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Stephan van Hulst
Saloon Keeper
Posts: 7808
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't understand your explanation. Please make it more detailed.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7808
142
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7808
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 7808
142
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Glad it helps.

Lists are actually very very useful, I couldn't think of writing applications without them. I think it's best to learn about them as soon as possible.

For now, initialize a list like this:

Add a partition to the list like this:

You can iterate over all partitions within a list like this:
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!