Recursively divide a list that each iteration divides into two parts to get the closest sum overall

Question

Given a list of numbers L = { a1, a2, a3, a4, ... , aN}

The problem is to divide this L into two parts, not just once but recursively until it becomes atomic. The main idea is like this post but adding the recursion thing.

(added: June 9) For example, if we have L = {10, 20, 1, 2} (edited: June 10) the solution might be, first, divide it to {10, 1, 2} and {20}, then divide the former into {1, 2} and {10}, keep going with {1, 2} to {1}, {2}. Now all the members of L are now atomic unable to be divided anymore.

After being divided, it should look like a binary tree of some sort.

Let's say it look like this..

  (a1 a2 a3 a4)
       /\
      /  \
     /    \
    /      \
 (a1 a2) (a3 a4)
   /\      /\
  /  \    /  \
(a1)(a2)(a3)(a4)

At each node the similarity function is

abs( sum(left_child) - sum(right_child) ) / sum(itself)

I want to find an "optimized" way to divide the list (create the tree) according to the "summation" of this function. Note that at the top level this value might have more impact than the lower ones, so weights should be provided.

weight(level) * abs( sum(left_child) - sum(right_child) ) / sum(itself)

let level is the level of this node in the binary tree.

I think it is possible to solve this using dynamic programming with the time complexity of O(2^N). However, this solution seems to be too slow for me. Anyone has any better solutions ?

Both optimization and approximation are welcome as well.

Thank you in advance.

Answer 1

An O(n) time complexity but really inaccurate approach would be:

def distance(a, b):
    return abs(a - b)

def balancedSlice(myList):

    total = sum(myList)
    a = 0        #a, b are the sum's of each slice
    b = total
    dist = distance(a, b) # current distance between slices
    for i in range (len(myList)):
        a += myList[i]
        b -= myList[i]
        if dist <= distance(a, b):
            return myList[:i],myList[i:] #list sliced "from 0 to before i" and "from i to end"
        dist = distance(a, b)

Another, a bit more accurate but not perfect, greedy algorithm in O(n log n):

def balancedSlice(myList):
    list1 = list()
    list2 = list()
    myList = list(myList) #skip if you can destroy the original list.
    myList.sort() # O(n log n)
    while myList:
        item = myList.pop()
        if sum(list1) <= sum(list2):
            list1.append(item)
        else:
            list2.append(item)
    return list1, list2

However, as stated here, this is an NP problem so if your list is big enough and you can tolerate imperfect results, you should stick to something like this greedy algorithm.