# 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


```python

```



## Recursive w/ Memoization


```python

```

## Imperative


```python
# 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):
    
                    

        
    
    
```

## Less imperative


```python
def partition()
```

## 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 


725d181cd5c18b2471af5dcf18f5998569c5c5d5
ipynb
Jupyter Notebook
algs/python/dp/partition_problem.ipynb
rencire/commoncs
82024060239a821f8439252e19cb0f3c2fecc385
MIT
2016-09-01T21:23:16.000Z
2016-09-01T21:23:16.000Z
algs/python/dp/partition_problem.ipynb
rencire/commoncs
82024060239a821f8439252e19cb0f3c2fecc385
MIT
algs/python/dp/partition_problem.ipynb
rencire/commoncs
82024060239a821f8439252e19cb0f3c2fecc385
MIT
Qwen/Qwen-72B
1. YES
2. YES