Just last night I was reading a book which had a chapter on the Partition Problem; the Partition Problem is basically about splitting a set of numbers into two smaller sets of equal size.
To visualize it, the book contained the following picture:
It shows how, given an input of k boxes, each with height n, you can create two stacks of boxes, each stack with half the height of the original stack (well, in this diagram, pile.)
If you were to write a function to do this, it might look something like:
>>> k = [3,4,3,1,2,3,3,2,1] [3,4,3,1,2,3,3,2,1] >>> partitionSolve(k) [ [3,3,2,3], [1,4,2,3,1] ] >>> sum(partitionSolve(k)) == sum(partitionSolve(k)) True
But this only solves for two stacks! What if we wanted to split the input into three equal stacks? Then we'd have to write another function!
>>> partitionSolveThree([3,4,3,1,2,3,3,2]) [ [3,4], [3,1,3], [2,3,2] ]
In fact, I want to be able to solve for N stacks:
>>> partitionSolveN(3, [2,1,1,2,3,1,2]) [ [2,2], [1,1,2], [3,1] ] >>> partitionSolveN(4, [2,1,1,2,3,1,2]) [ [2,1], [1,2], , [1,2] ]
But, I'm lazy, and I don't want to have to start some language's shell every time I want to use this function, so I decide to create a program to do it for me.
The problem is, I can't figure out an efficient way to do it!
Design a program which can solve the above problem, for any number N.
Your program should take input via stdin, and print its output to stdout.
C:\> echo 2343123321| solution.X 3323 14231
Input will be a single string of digits; the first specifying how many stacks the code should be broken into, and the rest represent the input stack. All numbers will be single digit, so you can think of it as a list delimited by empty strings (
The first character of input will be the N to solve for, so if the first character is a 6 your program will be expected to output 6 valid subsets, or an error. This number will always be between 1 and 9.
The rest of the input is the starting list, from which the sublists must be created. Each digit in here can be between 1 and 9, and they must all be used once and only once in the outputted sublists.
Output should then be a new-line delimited list of your output stacks, each stack should just be a sequence of the numbers within it.
Another few examples:
C:\> echo 334323321| solution.X 34 313 232 C:\> echo 3912743471352| solution.X 121372 97 4453 C:\> echo 92| solution.X forty-two
If the given input has no solution, your program can print any error message it wants, as long as there are no digits in the error message.
Fewest number of bytes wins! Good luck!