Breaking of a String CLR 5-9

splitstring.py

#!/bin/python
import sys

def splitstr(n,cut_list):
    if len(cut_list) == 0: 
        return [0,[]]
    min_positions = []
    min_cost = sys.maxint
    for k in cut_list:
        left_split = [ x for x in cut_list if x < k]
        right_split = [ x-k for x in cut_list if x > k] 
        print "left split => ", left_split,"right_split =>", right_split
        lcost = splitstr(k,left_split)
        rcost = splitstr(n-k,right_split)      
        cost = n+lcost[0] + rcost[0]
        positions = [k] + lcost[1]+ [x+k for x in rcost[1]] 
        print "cost:", cost, " min: ", positions
        if cost < min_cost:
            min_cost = cost
            min_positions = positions
    return (min_cost, min_positions)

if __name__ == '__main__':
    print splitstr(20,[3,10,16])