L14 comb

Combinatorial Functions: 

Combinatorial Functions Recursion for problem solving

Enumerating Initial segments (prefixes): 

Enumerating Initial segments (prefixes) inits [1,2,3] = [[],[1],[1,2],[1,2,3]] inits [2,3] = [ [], [2], [2,3] ] fun inits [] = [[]] | inits (x::xs) = []:: (map (fn ys =andgt; x::ys) (inits xs) ); fun inits [] = [[]] | inits xs = (inits (init xs))@[xs];

Enumerating Subsequences: 

Enumerating Subsequences subseq [2,3] = [[],[2],[3],[2,3]]; subseq [1,2,3] = [[], [1],[2],[3], [1,2],[1,3],[2,3],[1,2,3] ]; fun subseq [] = [[]] | subseq (x::xs) = let val ss = subseq xs in ss@(map (fn ys =andgt; x::ys) ss) end;

Enumerating permutations: 

Enumerating permutations perms [2] = [[2]] perms [1,2] = [[1,2], [2,1]] perms [0,1,2] = [[0,1,2],[1,0,2],[1,2,0], [0,2,1],[2,0,1],[2,1,0]] fun interleave x [] = [[x]] | interleave x (y::ys) = (x::y::ys) :: (map(fn xs=andgt;y::xs)(interleave x ys)); fun perms [] = [[]] | perms (x::xs) = foldr (op @) [] (map (interleave x) (perms xs)) ;

List partitions: 

List partitions The list of non-empty lists [L1,L2,…,Lm] forms a list-partition of a list L iff concat [L1,L2,…,Lm] = L [1,2] -andgt; [[[1,2]], [[1],[2]]] [0,1,2] -andgt; [ [[0,1,2]], [[0,1],[2]], [[0],[1,2]], [[0],[1],[2]] ]

Counting problem: 

Counting problem fun cnt_lp 0 = 0 | cnt_lp 1 = 1 | cnt_lp n = 2 * (cnt_lp (n-1)); (* cnt_lp n = 2^(n-1) for n andgt; 0 *) Property: cnt_lp (length xs) = (length (list_partition xs))

Constructing List Partitions: 

Constructing List Partitions fun lp [] = [] | lp (x::[]) = [ [[x]] ] | lp (y::x::xs) = let val aux = lp (x::xs) in (map (fn ss =andgt; [y]::ss) aux) @ (map (fn ss =andgt; (y::(hd ss)) :: (tl ss)) aux) end;

Set partition: 

Set partition The set of (non-empty) sets [s1,s2,…,sm] forms a set partition of s iff the sets si’s are collectively exhaustive and pairwise-disjoint. E.g., set partitions of {1,2,3} -andgt; { {{1,2,3}}, { {1}, {2,3}}, {{1,2}, {3}}, {{2}, {1,3}}, { {1},{2},{3}} } (Cf. list partition, number partition, etc.)

Divide and Conquer: 

(m-1)-partition of {2,3} Divide and Conquer m-partition of {1,2,3} 1 occurring with with a part in m-partition of {2,3} solitary part {1}:: 2-partitions of {1,2,3} = { { {1},{2,3}} } U { {{1,2},{3} } , { {2},{1,3} } }

Counting problem: 

Counting problem fun cnt_m_sp 1 n = 1 | cnt_m_sp m n = if m andgt; n then 0 else if m = n then 1 else (cnt_m_sp (m-1) (n-1)) + (m * (cnt_m_sp m (n-1))); Dependency (visualization) Basis: Row 1 and diagonal (Half-plane inapplicable) Recursive step: Previous row, previous column

(cont’d): 

(cont’d) upto 3 6 = [3,4,5,6] fun upto m n = if (m andgt; n) then [] else if (m = n) then [m] else m:: upto (m+1) n; fun cnt_sp n = foldr (op +) 0 (map (fn m =andgt; cnt_m_sp m n) (upto 1 n));

Constructing set partitions: 

Constructing set partitions fun set_parts s = foldr (op@) [] ( map (fn m =andgt; (m_set_parts m s)) (upto 1 (length s)) ); fun ins_all e [] = [] | ins_all e (s::ss) = (((e::s)::ss) :: ( map (fn ts =andgt; s :: ts) (ins_all e ss) ) );

Slide13: 

fun m_set_parts 1 s = [[s]] | m_set_parts m (s as hs::ts)= let val n = (length s) in if m andgt; n then [] else if m = n then [foldr (fn (e,ss)=andgt;[e]::ss ) [] s] else let val p1 = (m_set_parts (m-1) ts) val p2 = (m_set_parts m ts) in (map (fn ss =andgt; [hs]::ss) p1) @ (foldr (op@) [](map (ins_all hs) p2 )) end end;