Partition Problem
Terry Reedy
tjreedy at home.com
Mon Jul 16 23:18:03 CEST 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