This week's book giveaway is in the OCMJEA forum.
We're giving away four copies of OCM Java EE 6 Enterprise Architect Exam Guide and have Paul Allen & Joseph Bambara on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes Head is wrecked with this program! Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of OCM Java EE 6 Enterprise Architect Exam Guide this week in the OCMJEA forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Head is wrecked with this program!" Watch "Head is wrecked with this program!" New topic
Author

Head is wrecked with this program!

Alan Smith
Ranch Hand

Joined: Oct 19, 2011
Posts: 152

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

Joined: Aug 05, 2005
Posts: 3504
    
  14
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

Joanne
Alan Smith
Ranch Hand

Joined: Oct 19, 2011
Posts: 152

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

Joined: Aug 05, 2005
Posts: 3504
    
  14
That's still not true for this step
3 1
2 2

Mary Chellapa
Ranch Hand

Joined: Jul 26, 2011
Posts: 93
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


Mary
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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

Joined: Oct 19, 2011
Posts: 152

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
Bartender

Joined: May 31, 2011
Posts: 1776
it looks like "Achieving the given number in all possible ways(combination of digits) with the given number no. of digits"
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Head is wrecked with this program!