My Clojure explained solutions to the s99 problems 21 to 26
19/01/2011 Leave a comment
Insert an element at a given position into a list.
user> (insert-at(\c, 3, (list \a, \b, \d))
(\a, \b, \c, \d)
(defn insert-at "P21" [x i xs] (let [s (split-s99 i xs)] (concat (first s) (cons x (last s)))) )
This solution relies on the problem 17’s solution, i.e. the split function that breaks a list in two parts in a given index.
It starts by splitting the original list in two parts in the insertion index. The result is then constructed by concatenating the first half of the list, the element to insert and the second half.
Create a list containing all integers within a given range.
user> (range-s99 4 9)
(4 5 6 7 8 9)
(defn range-s99 "P22" [a b] (if (> a b) nil (cons a (range-s99 (+ 1 a) b))))
I’ve opted for a recursive solution: a range from “a” to “b” is the list with “a” as its first item and the range from “a+1” to b as the remaining items.
Extract a given number of randomly selected elements from a list.
user> (random-select 3 ‘(\a \b \c \d \e \f \g \h \i \j \k))
(\d \j \e)
(defn random-select "P23" [n xs] (let [r (remove-at (rand-int (count xs)) xs)] (if (= 1 n) (list (last r)) (cons (last r) (random-select (dec n) (first r))))))
This solution relies on the problem 20’s solution, i.e. the remove-at function that removes an item from a list in a given index, and returns the list composed of the remaining items and the removed item.
Randomly selecting “n” items from a list can be solved recursively by randomly selection one item from a list and then “n-1” items from the remaining list.
That’s exactly what the code posted above does: if “n” equals one, then remove a random element from the list using the remove-at function. the random index is obtained with the clojure predefined rand-int function. Otherwise, remove an item and add it to the list of selecting n-1 random items from the remaining list.
Lotto: Draw N different random numbers from the set 1..M.
Example: (lotto 6 49)
user> (19 39 31 35 10 41)
(defn lotto "P24" [n m] (random-select n (range-s99 1 m)))
This solution relies on the previous problem (23) and the problem 22’s solution: the function range-s99 is used to create a range from 1 to M, and then random-select is used to draw N random numbers from it.
Generate a random permutation of the elements of a list..
user> (random-permute ‘(\a \b \c \d \e \f))
(\a \e \f \b \d \c)
(defn random-permute "P25" [xs] (random-select (count xs) xs))
Again, this hardest part of this problem was already solved, in the problem 23: generating a random permutation of the elements of a list can be achieved by simply calling random-select to select n random elements from this list where n is the list’s size.
Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.
user> (permutations 2 ‘(\a \b \c \d))
((\a \b) (\a \c) (\a \d) (\b \c) (\b \d) (\c \d))
(defn permutations "P26" [n xs] (if (= 1 n) (map list xs) (reduce #(let [s (split-at (inc %2) xs) ps (permutations (dec n) (last s)) a (last (first s))] (concat %1 (map (fn [p] (cons a p)) ps))) '() (range 0 (inc (- (count xs) n)))) ))
A tough one. Again, recursivity is our friend.
I’ll explain the solution using examples starting with N=1 and then incrementing.
The permutations of size N=1 of a list (\a \b \c \d) are the list of individual elements as lists, i.e. ((\a) (\b) (\c) (\d))
The permutations of size N=2 of that same list can be computed as follows: for every element E of the list, compute the permutations of size N-1 among the elements coming after it (important, not the remaining elements) and add E to every permutation.
- Starting with \a, we compute the permutations of size 1 of (\b \c \d) which are ((\b) (\c) (\d)), and add \a to every one of them, which gives ((\a \b) (\a \c) (\a \d)).
- Then for \b, we compute the permutations of size 1 of the following elements, (\c \d) which are ((\c) (\d)) and add \b, yielding ((\b \c) (\b \d))
- For \c, we end up with ((\c \d))
- The last element is excluded as it has no following elements.
Combining all the partial results gives us the final solution.
The snippet above is the clojure transliteration of the process I described, generalized to handle arbitrary N values.