Home Original page

Partition Problem

Terry Reedy tjreedy at home.com
Mon Jul 16 17:18:03 EDT 2001 
"Donovan Hide" <donovanhide at bigfoot.com> wrote in message
news:9iv5e9$bru$1 at newsg1.svr.pol.co.uk...
> Hi,
>     thanks for the input, newsgroups are great! After scratching my head
> last night, I came up with a non-recursive algorithm which works for
> specific values of k (6 in the following example), as follows:
> from math import *
>
> def P(n,k):
>     res=[]
>     for a in range (n-k+1,int(ceil(n/k)-1),-1):
>         for b in range(a,0,-1):
>             for c in range(b,0,-1):
>                 for d in range(c,0,-1):
>                     for e in range(d,0,-1):
>                         for f in range(e,0,-1):
>                             if (a+b+c+d+e+f)==n:
>                                 res.append([a,b,c,d,e,f])
>
>     return res

Since k is fixed at 6 by the implementation, you really should *not*
pretend otherwise by putting it in the argument list.  Call this P6(n) and
add "k=6" as the first line.
[Or, check that k is 6 on input and "raise ValueError, 'arg k must be 6' "
if not.]

This nested for-loop solution will run much faster if you trim the branches
as soon as possible instead of just at the end after generating each of the
n**k leaves.

After
>         for b in range(a,0,-1):
add
              if (a+b+4) <= n: # in P(20,6) 15+2(or larger) cannot yield a
solution.
etcetera.  This is the branch-and-bound principle.  A better lower limit
than 1 (-1=0 in range) will also help.

Even better, do for b,c,d,e,f what you (almost) did for a: make the range
exact.  Start by defining remain_x as the amount (of the original n) that
remains to be partitioned *before* we assign a value to x.

remain_a = n
remain_b = n-a = remain_a - a
remain_c = n-a-b = remain_b - b
...
remain_f = ... = remain_e - e # this is the only possible value for f, no
loop needed
# if we proceed correctly, it will also be <= e, no test needed

Also let kx = <the number of parts remaining, including x>.  One upper
limit for x is remain_x - (kx-1) since each part after x will be at least
1.  Another, for monotinicity downward, is the value of the preceeding
part, if any.  So the upper limits for the range statements are

a:         remain_a - (k-1)
b: min(remain_b - (k-2), a)
...
e: min(remain_e - (k-5), d)

Letting kx = <the number of parts remaining, including x>, the lower limit
for x, again for monotinicity, is  remain_x/kx  + (remain_x % kx > 0).
Subtract 1 for range statement.
(remain_x - 1)/kx gives the same answer (after the subtraction).

[Note: since n/k is int, int(ceil(n/k)-1) = int(float(n/k)-1) = n/k-1 which
is 1 low for 20,6;
int(ceil(float(remain_x)/kx)-1) should give correct answer as above, but
float math is unnecessary.]

Putting this altogether gives us

def p6(n):
  k = 6
  res=[]
  i = 0
  remain_a = n
  for a in range (remain_a-(k-1), (remain_a-1)/k,-1):
    remain_b = remain_a - a
    for b in range(min(a,remain_b-(k-2)),(remain_b-1)/(k-1),-1):
      remain_c = remain_b - b
      for c in range(min(b,remain_c-(k-3)),(remain_c-1)/(k-2),-1):
        remain_d = remain_c - c
        for d in range(min(c,remain_d-(k-4)),(remain_d-1)/(k-3),-1):
          remain_e = remain_d-d
          for e in range(min(d,remain_e-(k-5)),(remain_e-1)/(k-4),-1):
            res.append([a,b,c,d,e,remain_e-e])
            i=i+1
  return res,i

[Note: since partitions are fixed sequences, they should better be returned
as tuples.]

Outfitting your P with a similar counter, both give a list of 90 lists and
we get

>>> P(20,6) == p6(20)
1

As for speed, P(50,6) takes 100 seconds on my machine (5427 partitions)
while p6(50) and even p6(70) (26207 partitions) take less that a second to
start printing.  P(70,6) would probably take hours to do the same.
Computing exactly what you want with nothing wasted is always best.

To solve this problem for any k using this approach, we could write a
program that will write and compile the python code for a particular value
of k (using x1 to xk instead of a to whatever).  [The underutilised ability
to do this sort of thing is a Lisp-like quality of Python.]

The new generator facility is a natural for combinatorial problems like
this.

Terry J. Reedy
More information about the Python-list mailing list