My Clojure explained solutions to the s99 problems 21 to 26

This post will present and, I hope, explain my solutions to the s99 problems 21 to 26. I’ve already posted the solutions and explanations for the problems 1-3, 4-7, 8-13 and 14-20.

P21

Insert an element at a given position into a list.
Example:
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.

P22

Create a list containing all integers within a given range.
Example:
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.

P23

Extract a given number of randomly selected elements from a list.
Example:
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.

P24

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.

P25

Generate a random permutation of the elements of a list..
Example:
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.

P26

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.

Example:
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.

About these ads

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: