Partition Problem

Eric Ren

Notes from Skiena, 2008.

Recurrence Relation

Let's start with the recurrence relation. Here is the math:

$$S = [s_1, s_1,..., s_n], s \in \mathbb{R} $$\begin{align} P(n, k) & = \min_{i=1}^{n} \max( P(i, k-1), \sum_{j=i+1}^n s_j ) \tag{0} \\ P(1, k) & = s_1 \tag{1} \\ P(n, 1) & = \sum_{i=1}^{n} s_i \tag{2} \end{align}

Unfortunately Python does not support pattern matching. Else we can write very idiomatic code that will look just like the recurrence above.

Now on to the different approaches:

Recursive



In [ ]:

Recursive w/ Memoization



In [ ]:

Imperative



In [6]:

    
# To better match the math equations above, collection starts at index 1 instead of 0

def partition(collection, n, k):
    if n == 0:
        return "No elements in collection to partition"
    
    
    # initialize matrix
    m = [[float('inf')] * k for _ in range(n+1)]
    d = [[-1] * k for _ in range(n+1)]
    
    # create prefix sums
    prefix_sum = [0] * (n+1)
    for i in range(1, n+1):
        prefix_sum[i] = prefix_sum[i-1] + collection[i]    
    
    # Base case from eq (1) above
    for i in range(1, n+1):
        m[1][i] = collection[1]
    
    # Base case from eq (2) above
    for i in range(1, n+1):
        m[i][1] = prefix_sum[i]
        
    
    # eq 0
    for i in range(2, n+1):
        for j in range(2, k+1):
            for x in range(1, i):
                cost = max(m[x][j-1].cost, prefix_sum[i]-prefix_sum[x])
                if m[i][j] > cost:
                    m[i][j] = cost
                    d[i][j] = x
                    
                    
          
    reconstruct_partition(collection, d, n, k)

    
    
def reconstruct_partition(collection, dividers, n, k):
    
    
    
    
def print_items(collection, start, end):









    



  File "<ipython-input-6-0a80a6f5be74>", line 46
    def print_items(collection, start, end):
      ^
IndentationError: expected an indented block

Less imperative



In [7]:

    
def partition()









    



  File "<ipython-input-7-50dd0a53b5a6>", line 1
    def partition()
                   ^
SyntaxError: invalid syntax

More "functional"

This probably is not efficient in python. But in languages that do optimize for tail recursion, this can result in the same performance as using loops.

Not enough memory... Generators to the rescue!

Now lets say that we can't initialize all that memory in the