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
- 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
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?