# L14 comb

44 %
56 %
Information about L14 comb
Entertainment

Published on June 17, 2007

Author: Crystal

Source: authorstream.com

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;

## Add a comment

 User name: Comment:

April 23, 2018

April 23, 2018

April 23, 2018

April 23, 2018

April 22, 2018

April 22, 2018

## Related pages

### Search › through l14 combo | Quizlet

If you're having trouble, want to report a bug, provide a suggestion, or just want to say hello — please fill out the form below.

### L14 S2 - Internal Comb. Engines - History 391 with ...

Study online flashcards and notes for L14 S2 - Internal Comb. Engines including Samuel Brown: 1823 Patent on the internal combustion engine Newcomen steam ...

### 12.1 L14 Comp Adv G from Trade F14 - COMPARATIVE ADVANTAGE ...

View Notes - 12.1 L14 Comp Adv G from Trade F14 from COMM 220 at Concordia Canada. COMPARATIVE ADVANTAGE & THE GAINS FROM TRADE The basic

### Conntek Transfer Switches L14 30P Locking ... - Amazon.com

Conntek Transfer Switches Cord / Temp Power Cord, L14-30P 30-Amp 4 Prong Locking Plug to CS6364 50-Amp Locking Female (25-Feet

### L14-SERIES HONEYCOMB DOORS - Columbus Door Co.

L14-SERIES L3-3 L-SERIES DOORS Universal Mortise Hinge Prep GENERAL NOTES: 1. Edge construction: • Vertical edges (both hinge and lock) are beveled with a

### Reliance Controls PB30 L14-30 30 Amp ... - amazon.com

The Reliance Controls PB30 NEMA 3R Power Inlet Box is an outdoor/watertight electrical inlet for a 30 Amp L14-30 generator cord. It is designed to be ...

### L14-StacksProcedures - Comp 120 Spring 2005 3/8 Lecture ...

View Notes - L14-StacksProcedures from COMP 120-a at UNC. Comp 120 Spring 2005 3/8 Lecture page 1 Stacks and Procedures I forgot, am I the Caller or

### Combo "できる日本語 初中級 L14 flashcards | Quizlet

Vocabulary words for Combo "できる日本語 初中級 L14. Includes studying games and tools such as flashcards.