Loco model for splitting a sequence of numbers into two equally-sized parts, minimizing the disparity of their sums

teamsplit.clj

(ns mark.teamsplit
  (:require [loco.core :as l]
            [loco.constraints :refer :all]))
          
; Although this problem was stated in terms of a group of players
; with multiple attributes, we can just represent each player by
; a single number, so this function just takes the list of numbers.

(defn find-teams
  "Players is a list of player strengths, timeout is in milliseconds"
  [players timeout]
  (let [n (count players),        
        team-vars (for [i (range n)] [:t i])
        ; For each player i, t_i is either -1 or 1, depending on team assignment.
        team-fd (for [v team-vars] 
                   ($in v -1 1)),
        ; Previous constraint says -1<=t_i<=1.  Now, we eliminate 0 as an option.
        not-zero (for [v team-vars]
                   ($!= v 0))
        ; Ensure the two teams are the same size, i.e.,
        ; the number of 1's equals the number of -1's, i.e.,
        ; they all add up to 0 (or can be off by one, if odd number of players)
        size-fd [($in :size-disparity -1 1)]
        same-size [($= (apply $+ team-vars) :size-disparity)]
        ; We create a variable representing the disparity to minimize.
        disparity-fd [($in :disparity 0 2147483646 :bounded)] ; might as well use largest int
        ; The formula for disparity.
        disparity [($= :disparity
                    ($abs ($scalar team-vars players)))]
        ; Build our model from all these constraints.
        model (concat
                team-fd not-zero size-fd same-size disparity-fd disparity),
        
        ; Find the solution, using the timeout.
        solution (l/solution model :minimize :disparity :feasible false :timeout timeout)
        
        ; Now, we'll need to interpret the return results, building the subsequences
        ; out of the -1 and 1 assignments.  For that, it will be useful to have players as vector.
        players (vec players)]
    
    {:team1
     (for [i (range (count players))
           :when (pos? (get solution [:t i]))]
       (players i)),
     :team2
     (for [i (range (count players))
           :when (neg? (get solution [:t i]))]
       (players i)),
     :disparity (:disparity solution)}))

;Usage:
;(find-teams [71 8 50 9 78 35 76 83 94 33 38 60 17 41 41 52 55 57 73 78 54 55 65 4] 1000)
;{:team1 (71 8 9 78 83 33 17 55 73 78 54 55), :team2 (50 35 76 94 38 60 41 41 52 57 65 4), :disparity 1}