Minimum Split

December 4, 2015

Today’s task is a simple exercise in list handling:

Given a list of integers, find the place where the list can be split in two that minimizes the differences in the sums of the two halves of the list. For instance, given the list [3,7,4,2,1], splitting after the second element of the list gives sums of 10 and 7 for the two halves of the list, for a difference of 3, and no other split gives a lower difference.

Your task is to write a program that splits a list as indicated above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

11 Responses to “Minimum Split”

  1. Rutger said

    In Python

    import sys
    
    # returns tuple (minimum_split, index to split on)
    # not so efficient w.r.t. memory/copying
    def minimum_split_lazy_coding(l):
    	return min((abs(sum(l[:i]) - sum(l[i:])), i) for i in range(0, len(l)))
    
    # returns tuple (minimum_split, index to split on)
    # traverses list only twice.
    def minimum_split_efficient(l):
    	sum_left = 0
    	sum_right = sum(l)
    	minimum = (abs(sum_right), 0)
    	for i in range(0, len(l)):
    		sum_left += l[i]
    		sum_right -= l[i]
    		difference = abs(sum_right - sum_left)
    		if difference < minimum[0]:
    			minimum = (difference, i+1)
    	return minimum
    
    
    
    
    examples = []
    examples.append([123])
    examples.append([3,7,4,2,1])
    examples.append([-1, -1])
    examples.append([-1, 1])
    examples.append([1,2,3,3,2,1])
    
    
    for e in examples:
    	print minimum_split_lazy_coding(e)
    	print minimum_split_efficient(e)
    
  2. John Cowan said

    It’s not very clear whether this means the minimum difference, or the minimum absolute value of the difference. The wording of page 2 suggests the latter, but page 1 doesn’t say so.

  3. Francesco said

    Haskell:

    import Data.List
    
    f x = minimumBy (\(_,a) (_,b) -> compare (abs a) (abs b)) a
        where a = zipWith (\a b -> ((a,b), sum a - sum b)) (inits x) (tails x)
  4. yaphats said

    Python:

    def bestSplit(lst):
    diff = 100000000
    idx = 0
    for count in range(0, len(lst)):
    if diff > abs(sum(lst[:count], 0) – sum(lst[count:], count)):
    diff = abs(sum(lst[:count], 0) – sum(lst[count:], count))
    idx = count
    return idx

  5. mcmillhj said
    fun split xs = let
        val sum = List.foldr (op +) 0 xs
        fun partial_sum [] total = []
          | partial_sum (x::xs) total = let
              val partial = total + x
          in
              partial :: partial_sum xs partial
          end
            
        fun min []      i res = ( res, i )
          | min (x::xs) i res = let
              val new_min = Int.abs(x - (sum - x))
          in
              if new_min < res then min xs (i+1) new_min
              else min xs i res 
          end
    in
        min (partial_sum xs 0) 0 (Int.abs sum)
    end
    [hunter@apollo: 12]$ poly --use minsplit.sml
    Poly/ML 5.2 Release
    > use "minsplit.sml";
    val split = fn : Int.int LIST.list -> Int.int * int
    val it = () : unit
    > split [3,7,4,2,1];
    val it = (3, 2) : Int.int * int
    > split [~1,1];
    val it = (0, 0) : Int.int * int
    > split [1,2,3,4,5];
    val it = (3, 3) : Int.int * int
    
  6. sc120 said

    Solution in Python

  7. sc120 said

    Third attempt in posting the code :p

    def list_sep(number_list):
        for i in xrange(1,len(number_list)):
            temp_diff=abs(sum(number_list[:i])-sum(number_list[i:]))
            if i== 1:
                diff=temp_diff
                position=i
            if temp_diff<diff:
                diff= temp_diff
                position=i
        return diff, position
    
    number_list=[3,7,4,2,1]
    
    print('Difference: %s' %list_sep(number_list)[0])
    print('Split position: %s' %list_sep(number_list)[1])
    
  8. Paul said

    In Python.

    from itertools import accumulate, chain
    def ssum(L):
        S = sum(L)
        return min((abs(S-2*a), i) for i, a in enumerate(chain([0], accumulate(L))))
    
  9. Eric Hansen said

    C++ attempt

    #include “math.h”
    #include
    std::vector numberList;
    numberList.push_back(3);
    numberList.push_back(7);
    numberList.push_back(4);
    numberList.push_back(2);
    numberList.push_back(1);

    std::vector differences;
    for(int split = 0; split < numberList.size(); ++split)
    {
    int leftSum = 0;
    for(int left = 0; left < split; ++left) {
    leftSum += numberList[left];
    }
    int rightSum = 0;
    for(int right = split; right < numberList.size(); ++right) {
    rightSum += numberList[right];
    }
    int difference = abs(rightSum – leftSum);
    differences.push_back(difference);
    }

    int lowestDiffIndex = 0;
    int lowestDiffValue = differences[0];
    for(int i = 0; i < differences.size(); ++i)
    {
    lowestDiffIndex = (differences[i] < lowestDiffValue) ? i : lowestDiffIndex;
    lowestDiffValue = (differences[i] < lowestDiffValue) ? differences[i] : lowestDiffValue;
    }
    // Split is at element lowestDiffIndex

  10. r. clayton said

    A solution in Racket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: