klassedelinger.sml

klassedelinger.sml

(* concatMap : ('a -> 'b list) -> 'a list -> 'b list
 * Forklaring:
 * f x = [y1,...,yn]
 * map f xs = [[a1,...,an], [b1,...,bn], ..., [z1,...,zn]]
 * concat (map f xs) = [a1,...,an,b1,...,bn,z1,...zn] *)
fun concatMap f xs = List.concat (map f xs)

(* foranNte x xss n: sætter x som det første element i den n'te liste i xss.
 * Eks.: foranNte 0 [[1,2],[3,4],[5,6],[7,8]] 2 = [[1,2],[3,4],[0,5,6],[7,8]]
 *)
fun foranNte x (xs::xss) 0 = (x::xs)::xss
  | foranNte x (xs::xss) n = xs::foranNte x xss (n-1)
  | foranNte _ _ _ = raise Subscript

(* foranHver x xss: genererer listen hvor x er sat foran hver liste i xss.
 * Eks.: foranHver 0 [[1,2],[3,4],[5,6]] =
 *           [[0,1,2],[3,4],[5,6],
 *            [1,2],[0,3,4],[5,6],
 *            [1,2],[3,4],[0,5,6]]
 *)
fun foranHver x xss =
    let val max = length xss - 1
        fun aux n =
            if n > max then []
            else foranNte x xss n :: aux (n+1)
    in aux 0 end

(* Fordi foranNte er curried og dens sidste argument er n, kan den anvendes
 * partielt sådan at foranNte x xss er en funktion som tager et n og giver
 * [xs1, xs2, ..., x::xsn, ...]. *)
fun foranHver x xss =
    List.tabulate (length xss, foranNte x xss)

(* klassedelinger løses rekursivt: Først findes klassedelinger for xs,
 * dernæst genereres alle kombinationer hvor x indsættes foran hver
 * liste (foranHver x ks) i alle klassedelingerne ks.
 * 
 * Sidst tilføjes den enkelte løsning hvor x, i stedet for at sættes
 * foran eksisterende lister, sættes i sin egen deling ([x]::ks).
 *
 * Eks.: klassedelinger [3] ~> [[[3]]]
 * Eks.: klassedelinger [2,3]
 *         ~> [[2], [3]] :: foranHver 2 [[[3]]]
 *         ~> [[2],[3]] :: [[[2,3]]]
 *         ~> [[[2],[3]], [[2,3]]]
 * Eks.: klassedelinger [1,2,3] (brug af resultatet fra klassedelinger [2,3])
 *         ~> [[1],[2],[3]] :: foranHver 1 [[2],[3]] @ foranHver 1 [[2,3]]
 *         ~> [[1],[2],[3]] :: [[[1, 2], [3]], [[2], [1, 3]]] @ [[[1,2,3]]]
 *         ~> [[[1],[2],[3]], [[1, 2], [3]], [[2], [1, 3]], [[1,2,3]]]
 *)
fun klassedelinger [] = []
  | klassedelinger [x] = [[[x]]]
  | klassedelinger (x::xs) =
    concatMap (fn ks => ([x]::ks)::foranHver x ks) (klassedelinger xs)