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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
11 Comments »

11 Responses to “Minimum Split”

  1. Rutger said
    December 4, 2015 at 11:07 AM

    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
    December 4, 2015 at 12:33 PM

    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
    December 4, 2015 at 5:32 PM

    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
    December 4, 2015 at 6:49 PM

    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
    December 4, 2015 at 9:20 PM 
    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
    December 4, 2015 at 9:40 PM

    Solution in Python

  8. sc120 said
    December 4, 2015 at 9:50 PM

    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])
  9. Paul said
    December 5, 2015 at 9:34 PM

    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))))
  10. Eric Hansen said
    December 6, 2015 at 4:30 AM

    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

  11. r. clayton said
    December 9, 2015 at 8:55 PM

    A solution in Racket.

Leave a comment