Minimum Split
December 4, 2015
Before you look at the suggested solution, check what your solution does when given the list (5 -5).
Our algorithm considers each split from left to right, beginning with the split that has no items in the left split and the entire list in the right split. At each step, we move one item from right to left, recompute totals, and if the current difference is less than the current minimum, update the minimum. The algorithm stops when the list is exhausted or the difference drops to zero.
(define (min-split xs)
(let loop ((i 0) (lo 0) (los (list)) (hi (sum xs)) (his xs)
(best-point 0) (best-value (sum xs)))
(cond ((or (null? his) (= lo hi)) (split best-point xs))
((< (abs (- lo hi)) best-value)
(loop (+ i 1) (+ lo (car his)) (cons (car his) los)
(- hi (car his)) (cdr his) i (abs (- lo hi))))
(else (loop (+ i 1) (+ lo (car his)) (cons (car his) los)
(- hi (car his)) (cdr his) best-point best-value)))))
Here are some examples:
> (min-split '(2 7 3 1 4)) (2 7) (3 1 4) > (min-split '(1 2 4 7 3)) (1 2 4) (7 3) > (min-split '(5 -5)) () (5 -5)
We used sum and split from the Standard Prelude. You can run the program at http://ideone.com/2GOsm9.
Programming Praxis 
In Python
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.
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)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
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 * intSolution in Python
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])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))))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
A solution in Racket.