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:


We have the function SCORE(L) that computes score for a list.
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.
COMBINE is associative and commutative, i.e. COMBINE(A, COMBINE(B, C)) == COMBINE(COMBINE(A, B), C) and COMBINE(A, B) == COMBINE(B, A)
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 &lt; 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 &lt; 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?
In your formulation, you need to compute score of each reduced list individually. So, if there are 2^(n-1) possible reduced lists, you need to perform at least O(2^n) operations.

Unless you can figure out some restrictions or relations between scores of related lists (such as "longer lists always have better scores"), it will remain O(2^n) problem.