1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – David Richerby Aug 21 '18 at 22:17
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.