Partition Problem

[Terry Reedy]

"Donovan Hide" <donovan at sherbet.co.uk> wrote in message
news:tlavt7jeqqt7b3 at corp.supernews.co.uk...
> Wow, fascinating! The minds of two 'algorthmistas' battling the pros and
cons
> of there code and techniques. I can't tell you how interesting this is

Here is an iterative no-stack version of my recursive algorithm.  It is
based on iterative template algorithm 4.2.5 in Marvin Paul's *Algorithm
Design: A Recursion Transformation Framework*.  It simulates the k-1 nested
loops.  It is still based on the key ideas of your brute force version.

def parti(n, k):
  if not 1 <= k <= n: raise ValueError, "k must be in range [1,n]"
  if 1 == k: return [[n]]   # avoids useless calculation for k=0
  # if k==n: return [[1]*n] # test case for correctness
  #
  work = [0]*k # current partition
  minp = [0]*k # minimum for corresponding element
  n0 = n       # save for last remainder (worklist[0])
  k0 = k       # save for termination test
  p = n        # fake 'previous' part for first min()
  result = []
  #
  while 1:
    while k >= 2:
      k = k-1                # reduce now for calc & index use
      p = min(p, n-k)        # (n-(k-1)) before reduce k
      work[k] = p
      minp[k]  = (n+k)/(k+1) # (n+(k-1))/k before reduce k
      n = n - p
      #print n, k, work[k], minp[k]; raw_input('loop')
    work[0] = n
    result.append(tuple(work))
    while work[k] == minp[k]: # at min value
      n = n + work[k]
      k = k+1
      if k == k0: # we have exhausted top level
        return result
    p = work[k] = work[k] - 1
    n = n + 1
    #print n, k, work[k], minp[k]; raw_input('end')

In a few comparitive timings, this took 70-90% as long as the recursive
version.  Not much saving.  Probably harder to modify.

Terry J. Reedy