fork(1) download
copy 
  1. ; minimum split
  2.  
  3. (define (split n xs)
  4.   (let loop ((n n) (xs xs) (zs '()))
  5.     (if (or (zero? n) (null? xs))
  6.         (values (reverse zs) xs)
  7.         (loop (- n 1) (cdr xs) (cons (car xs) zs)))))
  8.  
  9. (define (sum xs) (apply + xs))
  10.  
  11. (define (min-split xs)
  12.   (let loop ((i 0) (lo 0) (los (list)) (hi (sum xs)) (his xs)
  13.              (best-point 0) (best-value (sum xs)))
  14.     (cond ((or (null? his) (= lo hi)) (split best-point xs))
  15.           ((< (abs (- lo hi)) best-value)
  16.             (loop (+ i 1) (+ lo (car his)) (cons (car his) los)
  17.                   (- hi (car his)) (cdr his) i (abs (- lo hi))))
  18.           (else (loop (+ i 1) (+ lo (car his)) (cons (car his) los)
  19.                       (- hi (car his)) (cdr his) best-point best-value)))))
  20.  
  21. (call-with-values
  22.   (lambda () (min-split '(2 7 3 1 4)))
  23.   (lambda (los his)
  24.     (display los) (newline)
  25.     (display his) (newline)))
  26.  
  27. (newline)
  28.  
  29. (call-with-values
  30.   (lambda () (min-split '(1 2 4 7 3)))
  31.   (lambda (los his)
  32.     (display los) (newline)
  33.     (display his) (newline)))
  34.  
  35. (newline)
  36.  
  37. (call-with-values
  38.   (lambda () (min-split '(5 -5)))
  39.   (lambda (los his)
  40.     (display los) (newline)
  41.     (display his) (newline)))
Success #stdin #stdout 0s 7272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(2 7)
(3 1 4)

(1 2 4)
(7 3)

()
(5 -5)
https://ideone.com/2GOsm9
language:
Scheme (chicken 4.13)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!