Python number line cluster exercise

Question

I am working through an exercise in my textbook (Ex 4.7) and am implementing the code in Python to practice dynamic programming. I am having some trouble actually executing Algorithm 4.8. I understand what is going on until I get to 'Otherwise range s from 1 to t-1 and set s to minimize f(s). Why is the book using s in the for loop as well as setting it to the function f(s)? How should one go about implementing that line in Python?

[current code at bottom]

My current code is this so far:

x = [1,2,5,6,10]
k = 3
n = 5

r = [[0 for x in range(k)] for x in range(n)]
c = [[0 for x in range(k)] for x in range(n)]

def Union(lst1, lst2):
    final_list = lst1 + lst2
    return final_list

for j in range(k):
    for t in range(n):
        if j == 0:
            r[t][j] = (x[t]-x[0])/2
            c[t][j] = [(x[t]+x[0])/2]
        else:
            for s in range(t-1):
                f = max(r[s][j-1], (x[t]-x[s+1])/2)
                #set s to minimize f??
                r[t][j] = f
                w = []
                w.append((x[t]+x[s+1])/2)
                if c[s][j-1] == 0:
                    c[t][j] = w
                else:
                    c[t][j] = Union(c[s][j - 1], w)

print(r)
print(c)

Any help is much appreciated!

Answer 1

The algorithm is very good. My code is as follow.

x = [1,2,5,6,10]
k = 3
n = 5

r = [[[] for _ in range(k)] for _ in range(n)]
c = [[[] for _ in range(k)] for _ in range(n)]


def f(s, j_down, t):
    return max(r[s][j_down], (x[t]-x[s+1])/2.)

def get_min_f_and_s(j_down, t):
    """ range s from 1 to t-1 and set s to minimize f(s) 
    for example t=5 and j=3, so s range from 1 to 4, if f(1)=0.5, f(2)=0.4, f(3)=0.1, f(4)= 1.0, so f(4) is min one and s=2.
    And r[5][j] = f(2).
    """
    items = [(s, f(s, j_down, t))for s in range(t)]
    s, min_f = min(items, key=lambda x:x[1])
    return s, min_f

for j in range(k):
    if j == 0:
        for t in range(n):
            for t in range(n):
                r[t][j] = (x[t]-x[0])/2.0
                c[t][j] = [(x[t]+x[0])/2.0]
    else:
        for t in range(1, n):
            s, min_f = get_min_f_and_s(j-1, t)
            r[t][j] = min_f

            c[t][j] = c[s][j-1] + [(x[t]+x[s+1])/2.,]

print(r[-1][-1])
print(c[-1][-1])

A advice : When don't understand algorithm, you can run it by hand in scratch paper, maybe you will figure out how it work.