Integer partitioning in Java

Question

I'm trying to implement a program that returns the number of existing partitions of an integer n as part of an assignment. I wrote the code below, but it returns the wrong number (Partitions n returns the result of Partitions n-1). I don't get why this happens. I've tried many things and still don't know how to fix it, can anyone please help me?

[edited code out to avoid plagiarism from my colleagues :p]

m stands for the biggest number allowed in a partition, so partition(4,4) would be 5 = 4, 3+1, 2+2, 2+1+1, 1+1+1+1, but partition (4,1) would be 1 = 1+1+1+1. Execution: java Partitions n

@JacobG. A partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. more here: en.wikipedia.org/wiki/Partition_(number_theory) — Bruna
– Bruna, Commented Jun 4, 2017 at 22:22
else if (n <= 1 | m == 1) should probably be else if (n <= 1 || m == 1) — KevinO
– KevinO, Commented Jun 4, 2017 at 22:23
You've written partition as a function of two integers n and m (besides the memoization array, which also stores a function of two integers). I'm sure you had a good reason for this, but the rest of us don't know what the definition of your partition(n,m) is. — ajb
– ajb, Commented Jun 4, 2017 at 22:29
I'm editing the question to clarify it. m stands for the biggest number in the partition, so partition(5, 5) would be 7 = 5, 4 +1, ... 1 + 1 + 1 + 1 + 1 and partition (5, 1) would be 1 = 1 + 1 + 1 + 1 + 1 I did it because the assignment is a derivation from introcs.cs.princeton.edu/java/23recursion/Partition.java.html and they do that there — Bruna
– Bruna, Commented Jun 4, 2017 at 22:34

ajb · Accepted Answer · 2017-06-04 23:01:09Z

2

Suppose you're calling partitions(4,4,memo). As you said, the answer should be 5 because there are 5 ways to partition the integer:

4
3 + 1           <== counted by partition(1,3,memo)
2 + 2           <== counted by partition(2,2,memo)
2 + 1 + 1       <== counted by partition(2,2,memo)
1 + 1 + 1 + 1   <== counted by partition(3,1,memo)

So it looks like your algorithm tries to count the partitions in the way shown above... but is there one partition you're forgetting to count?

edited Jun 4, 2017 at 23:01

answered Jun 4, 2017 at 22:50

ajb

31.8k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ajb Over a year ago

Please be careful about how you fix it--my first attempt didn't work when I tried it. In particular, partition(4,2) needs to return 3.

Bruna Over a year ago

the simple way to solve it would be adding 1 to n right after parsing it in main, but i'm guessing that's the lazy way. i'm trying to find another one now

Collectives™ on Stack Overflow

Integer partitioning in Java

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related