(** [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 bags = createBags [] 2 in (* create bag of bags *)
let lst2 = List.sort descCompare lst in (* sort desc *)
let smallestHelper baglst = getSmallestBagSumIndex baglst max_int 0 0 in
(*create iterator helper *)
let handleNextValue value =
value ::(List.nth bags (smallestHelper bags)) in
let matchBagsTo lst3 =
match lst3 with
| [] -> bags
| h::t -> handleNextValue h and matchBagsTo t





let multi_partition n lst =
failwith "Unimplemented";;



partition [4;5;6;7;8]