The Partition Problem - Sorting Stacks of Boxes

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)[0]) == sum(partitionSolve(k)[1])
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], [3], [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.

Example:

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!

• Is it acceptable to not print anything at all if there's no solution? Apr 6 '15 at 10:37
• @FUZxxl Why do you keep saying this? NP-complete means there are no polynomial time solutions, but doesn't exclude algorithms faster than brute force in general.
– orlp
Apr 6 '15 at 11:14
• @FUZxxl Also, since the boxes are of size 1-9, I'm not even sure it's NP complete.
– orlp
Apr 6 '15 at 11:16
• @theonlygusti Please disallow boxes of size 0. It just adds more tedious code while not complicating the problem in any interesting way.
– orlp
Apr 6 '15 at 12:52
• @theonlygusti But it's entirely trivial. It doesn't add complexity, only annoyance.
– orlp
Apr 6 '15 at 13:38

Python 2, 321317321 319

import itertools as l
t=raw_input();e=0;g=l.permutations(int(k)for k in t[1:])
try:
while not e:
a=list(g.next());c=[sum(a[:i+1])for i in range(len(a))];s=c[-1];d=int(t[0]);f=s/d;assert f*d==s;r=range(f,s,f);e=set(r)<=set(c);b=[kfor k in a]
for k in r[::-1]:b.insert(c.index(k)+1,'\n')
print ''.join(b)
except:''


Some examples:

echo 43 | python part.py

echo 3912743471352 | python part.py
9124
7342
7135

echo 342137586 | python part.py
426
138
75


Thanks to theonlygusti for fixing the stdin input, and shaving off some chars and to Maltysen for pointing out a typo.

• Great! It works manually, but for my bulk tester the input needs to be taken from STDIN; if you replace t=sys.argv[1] with t=raw_input() it will then work properly, and also save a few bytes along the way; I think you can knock off that import sys. Apr 6 '15 at 17:29
• Why does the second example have 3 3's in the output, but only two in the input? Apr 6 '15 at 18:23
• Oh I thought the 3 upfront should also be part of the solution. Guess there are some adjustments to make Apr 6 '15 at 18:26
• But then why doesn't it happen in your other solutions? Apr 6 '15 at 18:27
• Should be ok now Apr 6 '15 at 18:46

Pyth - 73 69 bytes

Updated to match Pyth 4.0

Yay! Finally translated it. Likely huge room for golfing., but will be working on explanation. Finished explanation.

KmsdzJ.(KZFN*.pK.cUKtJ=km?:hNhdedgedZ>hNhdC,+]ZeN+eN]_1Iql{msdk1kB)EG


Uses brute force solution with a lot of help from itertools. Not really looking to golf any further because will be translating to Pyth.

from itertools import*
K=list(map(int,input()))
J=K.pop(0)
for N in product(permutations(K),combinations(range(len(K)),J-1)):
k=[N[0][s:e]if e>=0 else N[0][s:]for s,e in zip((0,)+N[1],N[1]+(-1,))]
d=list(map(sum,k))
if d.count(d[0])==J:print(k);break
else:print()


It takes cartesian product to make all possible options of arrangements of input (uses perms) and all possible slices (uses combs). Then it checks and breaks on the first one and then prints.

K               K=
m              Map
sd            Convert to integer
z             Over the input
J               J=
.(             Pop from index
K             K
Z             Index zero
FN              For N in
*              Cartesian Product
.p            Permutations full length
K            K
.c            Combinations no replace
UK           Of range(len(K))
tJ           Length J-1
=k             Set k=
m             Map with d as loop var
?    gedZ    If d>=0 (hack to get around Pyth has no None slice index)
:hN         Slice N[0]
hd         From k[0]
ed         Till k[-1]
>hN         Else slice N[0]
hd         From k[0] till end
C,           Zip (This makes the partitioning index pairs)
+]ZeN       [0]+N[-1]
+en]_1      N[-1]+[-1] (Again, the -1 is for the hack)
Iql{    1     If the set has len 1
msdk      Map sum to k
k            Implicitly print k
B            Break and implicitly close out if
)              Close out for loop
E               If we didn't break (Uses for-else construct in Python)
G              Print alphabet as error message


Works on all the inputs, except it froze my computer on the really big one but should in theory.

Note: does not work on the online interpreter because it has a timeout.

Now the set thing give both a speed and bytes improvement so you can run it online: Try it here.

• Just thought you should know - I'm making a change to Pyth that will break most past programs, including this one. Lambda parameters will only increment if the function is nested. It should be easy to update this, though. I think you only need to update the variables for m. Apr 8 '15 at 0:50
• K, that seems like a good idea, ill update my most recent answers and all unaccepted ones if I find the time. Apr 8 '15 at 0:53
• Your code does not give a correct answer for for instance 3121231223 Apr 8 '15 at 4:42
• @willem I don't think 3121231223 has a solution. It sums to 17 which is not divisible by3 . Apr 8 '15 at 6:09
• Ok, is this Python 3? In my case I had trouble with the n,*L= and it still prints the last k from the loop when there should be no number output in that case Apr 8 '15 at 18:54

Mathematica 154

f@n_:=Module[{g=IntegerDigits@n,d,a,r,s},d=First@g;a=Rest@g;
FirstCase[Subsets[Cases[Subsets@a,x_/;Tr@x==Tr@a/d],{d}],x_/;Sort[Join@@x]==Sort@a]];
f@Input[]


Standard input is entered by

f@Input[]


Examples with predetermined inputs:

f[334323321]


{{3, 4}, {3, 3, 1}, {3, 2, 2}}

f[3912743471352]


{{9, 7}, {7, 4, 5}, {1, 2, 4, 3, 1, 3, 2}}

f[342137586]


{{4, 8}, {7, 5}, {2, 1, 3, 6}}

f[42112312]


{{3}, {2, 1}, {2, 1}, {2, 1}}

Pyth, 72 Bytes

Such a close byte count to the other Pyth, but a completely different approach.

KmvdzJ.(K0=H/sKJ=KSK=JlKWK=NK=G])Fd_NIgHs+dGaG.(KxKdIqHsGaYGB;?YqJsmldYb


It is roughly equal to the following program, which was made through rethinking and slimming down my last answer (my last program didn't guarantee an answer):

Python 2, 242 Bytes

x=list(map(int,raw_input()))
y,S,b=x.pop(0),sum,[]
x.sort(reverse=1)
j,z,c=S(x)/y,len(x),0
while x:
k,a=x[:],[]
for i in k:
if j>=S(a)+i:a.append(x.pop(x.index(i)))
if S(a)==j:b.append(a);c+=len(a)
if c==z:
for o in b:print o
else:print


Basic idea for solving without using permutations

• Each stack must add up to k = sum of all boxes / n
• When the list of all boxes is sorted from greatest to least, you can iterate over that list, adding/popping boxes to a stack so that k >= stack remains true. Once stack == k, that stack is 'finished' and can be added to a list of the solutions. It is clear why this works when you examine the solution it produces:

input: 3912643473522
output: [[9, 7], [6, 5, 4, 1], [4, 3, 3, 2, 2, 2]]

• At the end, check if # of boxes in all solution stacks == length of input - 1 to see if all boxes were used, if not the input has no solution.

• The Python is incorrect: Try it online!. (The Pyth answer doesn't work in the versions of Pyth I tried, but as it uses the same algorithm I assume it's incorrect too.) The issue is that your algorithm sometimes sorts an answer onto the wrong stack and then cannot move it.
– user62131
Apr 17 '17 at 9:18

05AB1E, 11 bytes

ć.Œʒ€SOË}н»


Explanation:

ć            # Extract the head of the (implicit) input;
# pushing remainder and head separately to the stack
#  i.e. 2341 → 341 and 2
.Œ          # Get all possible combinations of head amount of parts from the remainder
#  → [[341,""],[34,1],[31,4],[3,41],[41,3],[4,31],[1,34],["",341]]
ʒ         # Filter this list of parts by:
€S       #  Convert the two parts to lists of digits
#   i.e. [341,""] → [[3,4,1],[]]
#   i.e. [31,4] → [[3,1],[4]]
O      #  Take the sum of each digit-list
#   → [8,0]
#   → [4,4]
Ë     #  Check if both are equal
#   → 0 (falsey)
#   → 1 (truthy)
}н   # After the filter: leave the first result
#  i.e. [[31,4],[4,31]] → [31,4]
»  # Join it by newlines (which is output implicitly as result)
#  → "31\n4"


If a list was allowed as output, it could have been 9 bytes instead:

ć.Œ.Δ€SOË


Where the .Δ is a builtin for find_first, (which could have been used in the original 11-byter as well for the same byte-count, but filter ʒ with leave first н apparently is slightly faster for the given test cases).