File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Head is wrecked with this program!

 
Alan Smith
Ranch Hand
Posts: 185
Firefox Browser Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 3742
16
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 3742
16
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's still not true for this step
3 1
2 2

 
Mary Chellapa
Ranch Hand
Posts: 93
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20203
26
MySQL Database
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser Linux Netbeans IDE
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic