The Partition Problem - Sorting Stacks of Boxes

Question

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!

Your Task

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!

Answer 1

Python 2, 321 317 321 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=[`k`for 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.

Answer 2

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.

Answer 3

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}}

Answer 4

05AB1E, 11 bytes

ć.Œʒ€SOË}н»

Try it online or verify all test cases.

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Ë

Try it online or verify all test cases.

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).

Answer 5

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

Try it here.

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.