# Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, optimally combining the score means minimizing, but that's probably not important

Formally stated:

1. We have the function SCORE(L) that computes score for a list.
2. Each adjacent pair of list elements L[i],L[i+1] can be replaced by element produced by the function COMBINE(L[i],L[i+1]). This operation can be repeated recursively, further shortening the list.
3. COMBINE is associative and commutative, i.e. COMBINE(A, COMBINE(B, C)) == COMBINE(COMBINE(A, B), C) and COMBINE(A, B) == COMBINE(B, A)
4. Given list L and functions SCORE/COMBINE, we need to find best score that can be reached on L or any its reduction.

So, as an example, if I have the list [A, B, C, D], all of these options are to be considered: (AB denotes the combination of A and B):

[A, B, C, D], [A, B, CD], [A, BCD], [A, BC, D], [AB, C, D], [AB, CD], [ABC, D], [ABCD]


Two obvious options include brute force (thanks, no) and a greedy algorithm, which would go roughly as follows in pseudocode Python:

def greedily_combine( elements, combine, score ):
i = 0
combine_success = False
while i < len( elements ) - 1:
combine_candidate = [combine( elements[i], elements[i+1] )]
sublist_to_consider = elements[0:i+1]
combined_score = score( combine_candidate )
uncombined_score = score ( sublist_to_consider )

if ( combined_score < uncombined_score ):
elements.pop(0)
elements.pop(0)
elements.insert(0, combine_candidate)
combine_success = True
else:
i += 1
if i == len( elements ) - 1:
i = 0
combine_success = False

return elements


However, this is almost certainly not going to be optimal. Is there a known general solution? If not, how could I have seen this myself, and is my greedy search good or easily improvable?

• Without restrictions on the score function, I don't see how there can possibly be a general algorithm that's better than brute force. If score is unrestricted, there's no way to tell in advance whether it's better or worse to combine two things so you'd have to try all possibilites. – David Richerby Aug 21 '18 at 22:17