Chapter XX Partition

DP and Karmarkar–Karp in OCaml

OCaml's records, immutable arrays, and pattern matching make the differencing heuristic read like its definition.

Subset-sum DP: a boolean array dp[w] = "is sum w reachable using some subset?" Iterate items; for each, update from high to low to avoid double-counting. The exact partition test is dp[total/2].

let can_partition (xs : int array) : bool =
  let total = Array.fold_left (+) 0 xs in
  if total mod 2 <> 0 then false
  else
    let target = total / 2 in
    let dp = Array.make (target + 1) false in
    dp.(0) <- true;
    Array.iter (fun x ->
      for w = target downto x do
        if dp.(w - x) then dp.(w) <- true
      done
    ) xs;
    dp.(target)

Karmarkar–Karp differencing: pop the two largest items, replace them with their absolute difference. Iterate until one number remains — that's the (approximate) partition gap. A min-heap keeps the largest at the top.

module H = Set.Make(struct
  type t = int let compare = compare
end)

let kk (xs : int array) : int =
  let h = ref (Array.fold_left (fun s x -> H.add x s) H.empty xs) in
  while H.cardinal !h > 1 do
    let max1 = H.max_elt !h in
    h := H.remove max1 !h;
    let max2 = H.max_elt !h in
    h := H.remove max2 !h;
    h := H.add (abs (max1 - max2)) !h
  done;
  H.min_elt !h

Combine. KK's residual is an upper bound on the optimal partition difference; the DP gives an exact answer for the decision problem. Use KK first as a screen — if KK returns 0, you have a perfect partition; otherwise call the DP.

let solve (xs : int array) =
  match kk xs with
  | 0 -> "perfect partition exists"
  | r when can_partition xs ->
      "perfect partition exists (KK gave " ^ string_of_int r ^ ")"
  | r ->
      "no perfect partition; KK upper bound = " ^ string_of_int r

04

Run it. KK runs in O(n log n) and gets within roughly n^(-α log n) of optimal on random inputs — astonishingly tight. For 1000-element instances with values up to 10⁹, KK is fast and almost always optimal; the DP would be infeasible at that size.
```
let () =
  let xs = [| 3; 1; 4; 1; 5; 9; 2; 6; 5; 3 |] in
  print_endline (solve xs)
```

Grammar — OCaml

OCaml is ML-family functional programming with strict evaluation and an industrial-strength compiler. Algebraic data types, pattern matching, and a Hindley–Milner type inferencer give you Haskell-like expressiveness with predictable performance.

let name = expr: binding. `let f x y = expr` defines a curried function (left-associative arrows).
let name : t = expr: typed binding. Most types are inferred, but you can annotate.
type t = ...: type definition. Sum types: `type color = Red | Green | Blue`.
match x with | p1 -> e1 | p2 -> e2: pattern matching. The compiler warns if your patterns are non-exhaustive.
[| a; b; c |]: array literal — semicolon-separated, mutable, fixed-size.
arr.(i): array indexed access. `arr.(i) <- v` assigns. Lists use square brackets and ::.
ref x: create a mutable cell holding x. Read with `!cell`; write with `cell := v`.
|>: pipeline: `x |> f` is `f x`. Same idea as Elixir or F#.
module M = ...: module — first-class collection of values, types, and submodules. Standard library modules: List, Array, Set, Map.

Sum an array with Array.fold_left. The fold takes a function (accumulator -> element -> new_accumulator), an initial value, and the array. Reads as a left-to-right reduction.

let total = Array.fold_left (+) 0 [| 3; 1; 4; 1; 5; 9; 2; 6 |]
(* total : int = 31 *)

(* same shape, different op: maximum *)
let largest = Array.fold_left max min_int [| 3; 1; 4; 1; 5; 9; 2; 6 |]
(* largest : int = 9 *)

Try OCaml — official, in-browser →