programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Head is wrecked with this program!

Alan Smith
Ranch Hand
Posts: 185
Hi,

so I am sitting at home bored and I see this little Java teaser on the net...

Write a number partitioner that partitions the number as follows for the number n where n can be any number:
eg. entered number is 4
4
3 1
2 2
2 1 1
1 1 1 1

basically breaking it down until you get to a print out of 1's equal to the sum of the entered number. It seems that you have to constantly take 1 away from the right most number in the list thats greater than 1 with the 1 that got taken away appended to the list. My idea is to use an arraylist to store the rows and wipe it for every row after printing out every value. It also looks like it will involve some recursion (which I am useless at). Any other pointers?

Thanks

Joanne Neal
Rancher
Posts: 3742
16
Mr Alan Smith wrote:It seems that you have to constantly take 1 away from the left most number in the list thats greater than 1 with the 1 that got taken away appended to the list.

That's not true of this step
3 1
2 2

or this step
2 2
2 1 1

Alan Smith
Ranch Hand
Posts: 185
Joanne Neal wrote:
Mr Alan Smith wrote:It seems that you have to constantly take 1 away from the left most number in the list thats greater than 1 with the 1 that got taken away appended to the list.

That's not true of this step
3 1
2 2

or this step
2 2
2 1 1

I meant right most number thats greater than 1. Edited!

Joanne Neal
Rancher
Posts: 3742
16
That's still not true for this step
3 1
2 2

Mary Chellapa
Ranch Hand
Posts: 93
• 1
sum of each row is n (here 4)
first separate it in one no ---> 4
then in two no ie ---> 3 1 and 2 2
then in three ---> 2 1 1
then 4 until n ... ---> 1 1 1 1

where no on right is less than or equal to no on left

now write that in code

Paul Clapham
Sheriff
Posts: 22834
43
First attempt:

Output 4.
Output 3 followed by all the partitions of 1.
Output 2 followed by all the partitions of 2.
Output 1 followed by all the partitions of 3.

And yes, that does involve recursion. But that would end like this:

1 3
1 2 1
1 1 1 1

which doesn't agree with the required output. So there's another restriction which has to be applied. Can you see what it is?

Alan Smith
Ranch Hand
Posts: 185
Paul Clapham wrote:First attempt:

Output 4.
Output 3 followed by all the partitions of 1.
Output 2 followed by all the partitions of 2.
Output 1 followed by all the partitions of 3.

And yes, that does involve recursion. But that would end like this:

1 3
1 2 1
1 1 1 1

which doesn't agree with the required output. So there's another restriction which has to be applied. Can you see what it is?

nope! Still trying to work it out.

John Jai
Rancher
Posts: 1776
it looks like "Achieving the given number in all possible ways(combination of digits) with the given number no. of digits"