5 people like it.

Like the snippet!

## Ninety-Nine F# Problems - Problems 21 - 28 - Lists again

These are F# solutions of Ninety-Nine Haskell Problems which are themselves translations of Ninety-Nine Lisp Problems and Ninety-Nine Prolog Problems. The solutions are hidden so you can try to solve them yourself.

### Ninety-Nine F# Problems - Problems 21 - 28 - Lists again

1: /// These are F# solutions of Ninety-Nine Haskell Problems 2: /// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), 3: /// which are themselves translations of Ninety-Nine Lisp Problems 4: /// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html) 5: /// and Ninety-Nine Prolog Problems 6: /// (https://sites.google.com/site/prologsite/prolog-problems). 7: /// 8: /// If you would like to contribute a solution or fix any bugs, send 9: /// an email to paks at kitiara dot org with the subject "99 F# problems". 10: /// I'll try to update the problem as soon as possible. 11: /// 12: /// The problems have different levels of difficulty. Those marked with a single asterisk (*) 13: /// are easy. If you have successfully solved the preceeding problems you should be able to 14: /// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of 15: /// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than 16: /// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. 17: /// You may need more time (i.e. a few hours or more) to find a good solution 18: /// 19: /// Though the problems number from 1 to 99, there are some gaps and some additions marked with 20: /// letters. There are actually only 88 problems.

### (*) Problem 21 : Insert an element at a given position into a list.

1: /// Example: 2: /// * (insert-at 'alfa '(a b c d) 2) 3: /// (A ALFA B C D) 4: /// 5: /// Example in F#: 6: /// 7: /// > insertAt 'X' (List.ofSeq "abcd") 2;; 8: /// val it : char list = ['a'; 'X'; 'b'; 'c'; 'd'] 9: 10: (Solution 1) 11: 12: (Solution 2)

### (*) Problem 22 : Create a list containing all integers within a given range.

1: /// Example: 2: /// * (range 4 9) 3: /// (4 5 6 7 8 9) 4: /// 5: /// Example in F#: 6: /// 7: /// > range 4 9;; 8: /// val it : int list = [4; 5; 6; 7; 8; 9] 9: 10: (Solution)

### (**) Problem 23 : Extract a given number of randomly selected elements from a list.

1: /// Example: 2: /// * (rnd-select '(a b c d e f g h) 3) 3: /// (E D A) 4: /// 5: /// Example in F#: 6: /// 7: /// > rnd_select "abcdefgh" 3;; 8: /// val it : seq<char> = seq ['e'; 'a'; 'h'] 9: 10: (Solution)

### (*) Problem 24 : Lotto: Draw N different random numbers from the set 1..M.

1: /// Example: 2: /// * (rnd-select 6 49) 3: /// (23 1 17 33 21 37) 4: /// 5: /// Example in F#: 6: /// 7: /// > diff_select 6 49;; 8: /// val it : int list = [27; 20; 22; 9; 15; 29] 9: 10: // using problem 23 11: (Solution) 12: 13: (Solution)

### (*) Problem 25 : Generate a random permutation of the elements of a list.

1: /// Example: 2: /// * (rnd-permu '(a b c d e f)) 3: /// (B A D C E F) 4: /// 5: /// Example in F#: 6: /// 7: /// > rnd_permu <| List.ofSeq "abcdef";; 8: /// val it : char list = ['b'; 'c'; 'd'; 'f'; 'e'; 'a'] 9: 10: (Solution 1) 11: 12: (Solution 2)

### (**) Problem 26 : Generate the combinations of K distinct objects chosen from the N elements of a list.

1: /// In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that 2: /// there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For 3: /// pure mathematicians, this result may be great. But we want to really generate all the 4: /// possibilities in a list. 5: /// 6: /// Example: 7: /// * (combinations 3 '(a b c d e f)) 8: /// ((A B C) (A B D) (A B E) ... ) 9: /// 10: /// Example in F#: 11: /// 12: /// > combinations 3 ['a' .. 'f'];; 13: /// val it : char list list = 14: /// [['a'; 'b'; 'c']; ['a'; 'b'; 'd']; ['a'; 'b'; 'e']; ['a'; 'b'; 'f']; 15: /// ['a'; 'c'; 'd']; ['a'; 'c'; 'e']; ['a'; 'c'; 'f']; ['a'; 'd'; 'e']; 16: /// ['a'; 'd'; 'f']; ['a'; 'e'; 'f']; ['b'; 'c'; 'd']; ['b'; 'c'; 'e']; 17: /// ['b'; 'c'; 'f']; ['b'; 'd'; 'e']; ['b'; 'd'; 'f']; ['b'; 'e'; 'f']; 18: /// ['c'; 'd'; 'e']; ['c'; 'd'; 'f']; ['c'; 'e'; 'f']; ['d'; 'e'; 'f']] 19: 20: (Solution 1) 21: 22: (Solution 2)

### (**) Problem 27 : Group the elements of a set into disjoint subsets.

1: /// a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 2: /// and 4 persons? Write a function that generates all the possibilities and returns them 3: /// in a list. 4: /// 5: /// Example: 6: /// * (group3 '(aldo beat carla david evi flip gary hugo ida)) 7: /// ( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) ) 8: /// ... ) 9: /// 10: /// b) Generalize the above predicate in a way that we can specify a list of group sizes 11: /// and the predicate will return a list of groups. 12: /// 13: /// Example: 14: /// * (group '(aldo beat carla david evi flip gary hugo ida) '(2 2 5)) 15: /// ( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) ) 16: /// ... ) 17: /// 18: /// Note that we do not want permutations of the group members; i.e. ((ALDO BEAT) ...) 19: /// is the same solution as ((BEAT ALDO) ...). However, we make a difference between 20: /// ((ALDO BEAT) (CARLA DAVID) ...) and ((CARLA DAVID) (ALDO BEAT) ...). 21: /// 22: /// You may find more about this combinatorial problem in a good book on discrete 23: /// mathematics under the term "multinomial coefficients". 24: /// 25: /// Example in F#: 26: /// 27: /// > group [2;3;4] ["aldo";"beat";"carla";"david";"evi";"flip";"gary";"hugo";"ida"];; 28: /// val it : string list list list = 29: /// [[["aldo"; "beat"]; ["carla"; "david"; "evi"]; 30: /// ["flip"; "gary"; "hugo"; "ida"]];...] 31: /// (altogether 1260 solutions) 32: /// 33: /// > group [2;2;5] ["aldo";"beat";"carla";"david";"evi";"flip";"gary";"hugo";"ida"];; 34: /// val it : string list list list = 35: /// [[["aldo"; "beat"]; ["carla"; "david"]; 36: /// ["evi"; "flip"; "gary"; "hugo"; "ida"]];...] 37: /// (altogether 756 solutions) 38: 39: (Solution)

### (**) Problem 28 : Sorting a list of lists according to length of sublists

1: /// a) We suppose that a list contains elements that are lists themselves. The objective 2: /// is to sort the elements of this list according to their length. E.g. short lists first, 3: /// longer lists later, or vice versa. 4: /// 5: /// Example: 6: /// * (lsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))) 7: /// ((O) (D E) (D E) (M N) (A B C) (F G H) (I J K L)) 8: /// 9: /// Example in F#: 10: /// 11: /// > lsort ["abc";"de";"fgh";"de";"ijkl";"mn";"o"];; 12: /// val it : string list = ["o"; "de"; "de"; "mn"; "abc"; "fgh"; "ijkl"] 13: /// 14: /// b) Again; we suppose that a list contains elements that are lists themselves. But this 15: /// time the objective is to sort the elements of this list according to their length 16: /// frequency; i.e.; in the default; where sorting is done ascendingly; lists with rare 17: /// lengths are placed first; others with a more frequent length come later. 18: /// 19: /// Example: 20: /// * (lfsort '((a b c) (d e) (f g h) (d e) (i j k l) (m n) (o))) 21: /// ((i j k l) (o) (a b c) (f g h) (d e) (d e) (m n)) 22: /// 23: /// Example in F#: 24: /// 25: /// > lfsort ["abc"; "de"; "fgh"; "de"; "ijkl"; "mn"; "o"];; 26: /// val it : string list = ["ijkl"; "o"; "abc"; "fgh"; "de"; "de"; "mn"] 27: 28: (Solution)

let insertAt x xs n =

let rec insAt acc xs n =

match xs, n with

| [], 1 -> List.rev (x::acc)

| [], _ -> failwith "Empty list you fool!"

| xs, 1 -> List.rev (x::acc) @ xs

| x::xs, n -> insAt (x::acc) xs (n - 1)

insAt [] xs n

let rec insAt acc xs n =

match xs, n with

| [], 1 -> List.rev (x::acc)

| [], _ -> failwith "Empty list you fool!"

| xs, 1 -> List.rev (x::acc) @ xs

| x::xs, n -> insAt (x::acc) xs (n - 1)

insAt [] xs n

let rec insertAt' x xs n =

match xs, n with

| [], 1 -> [x]

| [], _ -> failwith "Empty list you fool!"

| _, 1 -> x::xs

| y::ys, n -> y::insertAt' x ys (n - 1)

match xs, n with

| [], 1 -> [x]

| [], _ -> failwith "Empty list you fool!"

| _, 1 -> x::xs

| y::ys, n -> y::insertAt' x ys (n - 1)

let range a b = [a..b]

let rnd_select xs n =

let rndSeq = let r = new System.Random() in seq { while true do yield r.Next() }

xs |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> Seq.take n

let rndSeq = let r = new System.Random() in seq { while true do yield r.Next() }

xs |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> Seq.take n

let diff_select n m = rnd_select (seq { 1 .. m }) n |> List.ofSeq

let diff_select' n m =

let rndSeq = let r = new System.Random() in Seq.initInfinite(ignore >> r.Next )

seq { 1 .. m } |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> Seq.take n |> List.ofSeq

let rndSeq = let r = new System.Random() in Seq.initInfinite(ignore >> r.Next )

seq { 1 .. m } |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> Seq.take n |> List.ofSeq

// using problem 23

let rnd_permu xs = List.length xs |> rnd_select xs

let rnd_permu xs = List.length xs |> rnd_select xs

let rnd_permu' xs =

let rec rndSeq =

let r = new System.Random()

seq { while true do yield r.Next() }

xs |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> List.ofSeq

let rec rndSeq =

let r = new System.Random()

seq { while true do yield r.Next() }

xs |> Seq.zip rndSeq |> Seq.sortBy fst |> Seq.map snd |> List.ofSeq

// as a bonus you get the powerset of xs with combinations 0 xs

let rec combinations n xs =

match xs, n with

| [],_ -> [[]]

| xs, 1 -> [for x in xs do yield [x]]

| x::xs, n ->

[for ys in combinations (n-1) xs do

yield x::ys

if List.length xs > n then

yield! combinations n xs

else

yield xs]

let rec combinations n xs =

match xs, n with

| [],_ -> [[]]

| xs, 1 -> [for x in xs do yield [x]]

| x::xs, n ->

[for ys in combinations (n-1) xs do

yield x::ys

if List.length xs > n then

yield! combinations n xs

else

yield xs]

let rec combinations' n xs =

let rec tails = function

| [] -> [[]]

| _::ys as xs -> xs::tails ys

match xs, n with

| _, 0 -> [[]]

| xs, n ->

[ for tail in tails xs do

match tail with

| [] -> ()

| y::xs' ->

for ys in combinations' (n - 1) xs' do

yield y::ys ]

let rec tails = function

| [] -> [[]]

| _::ys as xs -> xs::tails ys

match xs, n with

| _, 0 -> [[]]

| xs, n ->

[ for tail in tails xs do

match tail with

| [] -> ()

| y::xs' ->

for ys in combinations' (n - 1) xs' do

yield y::ys ]

let rec group ns xs =

let rec combination n xs =

match n,xs with

| 0, xs -> [([], xs)]

| _, [] -> []

| n, x::xs ->

let ts = [ for ys, zs in combination (n-1) xs do yield (x::ys, zs)]

let ds = [ for ys, zs in combination n xs do yield (ys, x::zs)]

ts @ ds

match ns,xs with

| [], _ -> [[]]

| n::ns, xs ->

[ for g, rs in combination n xs do

for gs in group ns rs do

yield g::gs ]

let rec combination n xs =

match n,xs with

| 0, xs -> [([], xs)]

| _, [] -> []

| n, x::xs ->

let ts = [ for ys, zs in combination (n-1) xs do yield (x::ys, zs)]

let ds = [ for ys, zs in combination n xs do yield (ys, x::zs)]

ts @ ds

match ns,xs with

| [], _ -> [[]]

| n::ns, xs ->

[ for g, rs in combination n xs do

for gs in group ns rs do

yield g::gs ]

let lsort xss = xss |> List.sortBy Seq.length

let lfsort xss = xss |> Seq.groupBy (Seq.length) |> Seq.sortBy (snd >> Seq.length) |> Seq.collect snd |> List.ofSeq

let lfsort xss = xss |> Seq.groupBy (Seq.length) |> Seq.sortBy (snd >> Seq.length) |> Seq.collect snd |> List.ofSeq

### More information

Link: |
http://fssnip.net/ap |

Posted: |
2 years ago |

Author: |
Cesar Mendoza (website) |

Tags: |
Ninety-Nine F# Problems, tutorial, F#, lists |