Split An Array
January 23, 2018
We make two passes through the array, first determining the sum, and then, if the sum is even, splitting the array at the point where the sum is equal to half the sum of the whole array:
(define (split-equal xs)
(let ((n (sum xs)))
(if (odd? n) #f
(let loop ((xs xs) (n (/ n 2)) (ys (list)))
(cond ((null? xs) #f)
((zero? n) (values (reverse ys) xs))
((negative? n) #f)
(else (loop (cdr xs) (- n (car xs)) (cons (car xs) ys))))))))
Here are some examples:
> (split-equal '(1 2 3 4 5 6 21)) (1 2 3 4 5 6) (21) > (split-equal '(1 90 50 30 5 3 2 1)) (1 90) (50 30 5 3 2 1) > (split-equal '(50 100 1000)) #f
You can run the program at https://ideone.com/xwkQf3.
Programming Praxis 
A simple perl script – if we have a -ve sum we add the first value otherwise subtract the last…
sub splitable { my $s=0; $s+=$s<0?pop@_:-shift@_ while @_; return $s?0:1; }Here is a solution in R7RS Scheme and some SRFI-1 procedures (and SRFI
8 for receive). It finds all prefix-suffix pairs with equal sums. The
main idea is to sum the array left-to-right and right-to-left and look
for equality of elements at complementary positions.
(import (scheme base) (scheme write) (only (srfi 1) fold split-at iota filter-map) (srfi 8)) (define input-101 '(1 2 3 4 5 15)) ;; reverse of: sum of all prefixes of lst (including empty prefix) (define (reverse-prefix-sum/e lst) (fold (lambda (n psums) (cons (+ n (car psums)) psums)) '(0) lst)) ;; ((prefix suffix) ...) such that sum of prefix elements and sum of ;; suffix elements are equal. (define (split*/eq-sum lst) (let ((eq-indices (filter-map (lambda (i x y) (and (= x y) i)) (iota (length lst)) (reverse (reverse-prefix-sum/e lst)) (reverse-prefix-sum/e (reverse lst))))) (map (lambda (i) (receive (l r) (split-at lst i) (list l r))) eq-indices))) ;; examples (display (split*/eq-sum input-101)) (newline) (display (split*/eq-sum (cons 3 input-101))) (newline) (display (split*/eq-sum '(1 2 3 0 -1 -2 6 0 3))) (newline) (display (split*/eq-sum '(1 2 0 3 0 0 -1 -2 6 -2 0 -1 0 2 -2))) (newline)Here’s a solution in Python 3.
import itertools def split_array(l): s = sum(l) for idx, x in enumerate(itertools.accumulate(l), 1): if s - x == x: return l[:idx], l[idx:] return None l = [1, 2, 3, 4, 5, 15] print(split_array(l))Output:
Super simple JavaScript array.slice method
var arr = [1, 2, 3, 4, 5, 15];
console.log(arr.slice(0, 5));
console.log(arr.slice(5));
@Caz: I don’t see how your code might split an array to match the task. It does work for the given example. But I’m sure it’ll fail for arr = [1, 2, 3, 4, 5, 9]
Here’s a solution in C.
The function indicates success or failure with a return value, and passes the index of the split with an out parameter.
It returns early if the sum is odd or if the running sum is greater than the remaining sum.
#include <stdbool.h> #include <stdio.h> #include <stdlib.h> // The return value indicates success/failure. // The index of the split is saved in out parameter split_idx. bool split_array(int* array, size_t n, size_t* split_idx) { long sum = 0; for (size_t i = 0; i < n; ++i) sum += array[i]; // If sum is odd, there is no valid split. if (sum & 1) return false; long cumsum = 0; for (size_t i = 0; i < n; ++i) { cumsum += array[i]; long remsum = sum - cumsum; // remaining sum if (remsum == cumsum) { *split_idx = i + 1; return true; } // If cumulative sum is greater than remaining // sum, there is no valid split. if (remsum < cumsum) return false; } return false; } void print_array(int* array, size_t n) { printf("["); for (size_t i = 0; i < n; ++i) { if (i > 0) printf(", "); printf("%d", array[i]); } printf("]"); } int main(void) { int array[] = {1, 2, 3, 4, 5, 15}; size_t n = sizeof(array) / sizeof(int); size_t split_idx; int success = split_array(array, n, &split_idx); if (success) { print_array(array, split_idx); printf("\n"); print_array(array + split_idx, n - split_idx); printf("\n"); } else { printf("none\n"); } return EXIT_SUCCESS; }Output:
No problem today, hope all is well. For this one, if the array elements are all positive (so the cumulative sum is monotonic), then James’ idea of working in from both ends is good – if negative (or zero) elements are allowed, so there might be multiple solutions, can’t think of anything better than chaw’s approach.
Here’s a Haskell version.
-- Let xs = [x0, x1, x2, ..., xn] and xs[i,j] = xi+x(i+1)+...+xj. -- -- We have xs[0,i] + xs[i+1,n] == xs[0,n], for 0 ≤ i < n. -- -- So, finding an i such that xs[0,i] == xs[i+1,n] is equivalent to finding -- an i such that 2*xs[0,i] == xs[0,n]. -- -- If we let si = xs[0,i] then this can be stated as finding an i such that -- 2*si == sn, 0 ≤ i < n. Note that for i to exist sn must be even. -- -- If all xs are positive then s0, s1, ..., sn is a strictly increasing -- sequence, so we need only consider the si in order, until si equals or -- exceeds sn/2. If si == sn/2 then ([x0, ..., xi], [x(i+1), ..., xn]) is -- a valid partition, otherwise there is none. import Data.Bool import Data.Vector (Vector) import qualified Data.Vector as V equalSplit :: Integral a => Vector a -> Maybe (Vector a, Vector a) equalSplit xs | V.null xs = Nothing | otherwise = let (ss, sn) = (V.postscanl' (+) 0 xs, V.last ss) in if odd sn then Nothing else splIdx (sn `div` 2) ss >>= \i -> Just $ V.splitAt i xs splIdx :: Ord a => a -> Vector a -> Maybe Int splIdx sn ss = let (i, ge) = V.head $ V.dropWhile ((< sn) . snd) $ V.indexed ss in bool Nothing (Just $ i + 1) (ge == sn) test :: [Int] -> IO () test = print . equalSplit . V.fromList main :: IO () main = do test [] test [1] test [1, 2] test [1, 2, 3, 4, 5, 14] test [1, 2, 3, 4, 5, 15] test [1, 2, 3, 2, 3, 1]