Partition Problem

Terry Reedy tjreedy at home.com
Tue Jul 17 09:00:12 CEST 2001


"Arne Leithe" <arne at leithe.spammenot.no> wrote in message
news:Xns90E1337E8B341arneleitheno at 148.122.208.74...
> "Terry Reedy" <tjreedy at home.com> wrote in
> news:fSI47.12086$p7.3693169 at news1.rdc2.pa.home.com:
>
> > [...]
> > 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.
>
>
> I disagree :-)

My paragraph began "As for speed..." and the last sentence was written with
respect to that stated criterion.  Ignoring constant factors which come
into play  for 'small' problem size,  it is true.

>What's best in the majority of cases is an algorithm that's
> readable, maintainable, extensible etc.

Let's see: I added easy to understand  variables that allow one to apply
the principle he used for the range of the outermost forloop to all the
loops.  It is about as easy to read and much more extensible to larger
sums.  Increasing or decreasing k would be about as trivial with either
version.

>  If speed isn't an issue (and nobody
> said it would be an issue in this case), there would be no reason
> whatsoever to optimise it for speed at the cost of the criterias
mentioned
> above.

If he were to want 7 parts adding to 70, speed would very much be an issue.
Various people have said that Python is nice for developing algorithms, and
speed versus C less an issue than it at first seems, because it is so easy
to explore variations and maybe find a version that is orders of magnitude
faster.  So I developed and published a concrete example that would
illustrate this process.

> In fact, he stated very well what he wanted - the sets of six
> numbers to sum up to 17 (and 20).

For exactly these two small numbers, I could write or type the list in the
order produced
by my version of the nested for-loop algorithm in about the same time
needed to write, debug, and run a Python program.  If that is the limit of
the problem, why have people given multiple solutions, and done so in terms
of general n?

> Quite often, though, a more general solution is required.

So why do you object when I revise an algorith to make it feasible for much
larger n?
...
> What is important to avoid in any case, though, is repeating code where
the
> number of repetitions depend on one of the criterias (as b above). I pity
> such code, it's almost as it's alive and begs to be put it out of its
> misery.

As you already pointed out, Donovan's  'miserable' code solved his specific
problem.  There are many other problems whose obvious solution is a varible
number of nested loops.  If the loops are uniform (as I strove to make them
be), they represent a parameter-specific unrolling of a recursion which can
potentially be rolled back up into a more general recursive version.  In
the present case:

def p6(n):
  k = 6
  res=[]
  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((remain_e-e,e,d,c,b,a))
   return res

becomes, for instance

def part(n0, k0):
  if not 1 <= k0 <= n0: raise ValueError, "k must be in range [1,n]"
  global _part
  result = []
  worklist = [0]*k0
  def _part(n, k, previous, result=result, worklist=worklist):
    global _part
    if k == 1:
      worklist[0] = n
      result.append(tuple(worklist))
    else:
      k1 = k-1
      for p in range(min(previous, n - k1), (n-1)/k, -1):
        worklist[k1] = p
        _part(n-p, k1, p)
  _part(n0, k0, n0)
  return result

which gives an identical list at about 2/3rds the speed, but with the gain
of working for any valid k.

> Anyway, here is a new version of the algorithm I posted before, this time
> speed is considered and you can specify criterium b in the function. (You
> actually specify the maxiumum of slots in the solution - if zeros can be
> part of the solution the rest can be filled with zeros.)
>
> def Bags(res, max_pockets, start = 1):
> if max_pockets == 1: return [[res]]
>     return [[i] + bag for i in range(start, res / 2 + 1) \
>         for bag in Bags(res - i, max_pockets - 1, i)] + [[res]]

Is this supposed to give the same answers as part(res,max_pockets)?  (I am
still running 1.5.2 so I cannot check myself what it does do.)  If so,
neither 'res/2' nor  '+[[res]]' is obviously correct to me.

Terry J. Reedy






More information about the Python-list mailing list