concat.py

def concat_optimal(xs, i=0, j=None, cache=None):
	if cache is None:
		i, j, cache = 0, len(xs), dict()
	if (i, j) not in cache:
		cache[i, j] = concat_optimal0(xs, i, j, cache)
	return cache[i, j]

def concat_optimal0(xs, i, j, cache):
	if j == i+1:
		return 0, xs[i], i
	if j == i+2:
		return xs[i]+xs[i+1], xs[i]+xs[i+1], (i, i+1)
	best = 1e9, None, None
	for m in range(i, j-1):
		cost_left, length_left, parse_left = concat_optimal(xs, i, m+1, cache)
		cost_right, length_right, parse_right = concat_optimal(xs, m+1, j, cache)
		cost = cost_left + cost_right + length_left + length_right
		length = length_left + length_right
		parse = (parse_left, parse_right)
		if cost < best[0]:
			best = (cost, length, parse)
	return best

def concat_binary(xs, i=None, j=None):
	if j is None:
		i, j = 0, len(xs)
	if j == i+1:
		return 0, xs[i], i
	if j == i+2:
		return xs[i] + xs[i+1], xs[i] + xs[i+1], (i, i+1)
	m = (i + j) // 2
	cost_left, length_left, parse_left = concat_binary(xs, i, m)
	cost_right, length_right, parse_right = concat_binary(xs, m, j)
	cost = cost_left + cost_right + length_left + length_right
	length = length_left + length_right
	parse = (parse_left, parse_right)
	return cost, length, parse

def fmt_parse(p):
	if isinstance(p, tuple):
		return '(' + fmt_parse(p[0]) + '+' + fmt_parse(p[1]) + ')'
	else:
		return 's[%s]' % p

def printr(s, r):
	cost, _, parse = r
	print(s + ':', 'cost=%s' % cost, 'parse=%s' % fmt_parse(parse))

cases = [
	[1, 2, 3, 4, 5],
	[1, 2, 3],
	[3, 2, 1],
	[1, 5, 2, 6, 6, 7],
]
for c in cases:
	print('case', c)
	printr('optimal', concat_optimal(c))
	printr('binary', concat_binary(c))
	print('')