(** [lo -- hi] is the list containing the integers from [lo] to
[hi], inclusive.  For example, [0 -- 3] is [0; 1; 2; 3],
and [4 -- 3] is [[]]. The implementation is tail recursive. *)
let (--) lo hi =
let rec loop lo hi acc =
if lo > hi then acc
else loop (lo + 1) hi (lo :: acc)
in
List.rev (loop lo hi [])


let descCompare x y = if x<=y then 1 else -1;;




let addValueToBag lst value = [value] @ lst;;

let rec sumOfBag l=
match l with
[]->0
| head::tail-> head + (sumOfBag tail);;


let createBags bags n =
let addBagToBags x = []  in
List.init n addBagToBags


let rec getSmallestBagSumIndex bags lowSum index smallestIndex =
if index >= List.length bags then smallestIndex else
let thisSum = sumOfBag (List.nth bags index) in
if lowSum > thisSum then
getSmallestBagSumIndex bags lowSum (index +1) index
else
getSmallestBagSumIndex bags lowSum (index +1) smallestIndex ;;



let partition lst =
let rec bags = createBags 2 in (* create bag of bags *)
let lst2 = List.sort descCompare lst in (* sort desc *)
let rec handleNextValue value =
value ::(List.nth (getSmallestBagSumIndex bags max_int 0 0)) in (* create iterator helper *)
List.iter handleNextValue lst2;;







let multi_partition n lst =
failwith "Unimplemented";;



createBags [] 5;;

getSmallestBagSumIndex [[4];[3];[10];[1]] max_int 0 0;;