This is the first set that I’m not a 100% proud of. After being stuck on P26 for days, I just stole the code from clojure.contrib.combinatorics. At least I learned a few things! (defn-) creates a generator! Now I can create infinite sequences! Also, there is a better example of the #(%) syntax. The (cond …) syntax also looks useful, as now I can replicate JSP’s choose/when/otherwise.
; P23 (**) Extract a given number of randomly selected elements from a list. (defn rnd_select [n input] (if (> n 0) (loop [c n output '() [r x] (remove_at (rand-int (count input)) input)] (if (> c 0) (recur (dec c) (cons x output) (remove_at (rand-int (count r)) r)) output)) nil) ) ; P24 (*) Lotto: Draw N different random numbers from the set 1..M. ; The selected numbers shall be put into a result list. (defn lotto [n m] (rnd_select n (s99_range 1 m))) ; P25 (*) Generate a random permutation of the elements of a list. (defn randomPermute [input] (loop [c (count input) output '() [r x] (remove_at (rand-int (count input)) input)] (if (> c 1) (recur (dec c) (cons x output) (remove_at (rand-int (count r)) r)) (cons x output)))) ; P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list. (comment "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.") (defn- index-combinations [n cnt] (lazy-seq (let [c (vec (cons nil (for [j (range 1 (inc n))] (+ j cnt (- (inc n)))))), iter-comb (fn iter-comb [c j] (if (> j n) nil (let [c (assoc c j (dec (c j)))] (if (< (c j) j) [c (inc j)] (loop [c c, j j] (if (= j 1) [c j] (recur (assoc c (dec j) (dec (c j))) (dec j)))))))), step (fn step [c j] (cons (rseq (subvec c 1 (inc n))) (lazy-seq (let [next-step (iter-comb c j)] (when next-step (step (next-step 0) (next-step 1)))))))] (step c 1)))) (defn combinations "All the unique ways of taking n different elements from items" [n items] (let [v-items (vec (reverse items))] (if (zero? n) (list ()) (let [cnt (count items)] (cond (> n cnt) nil (= n cnt) (list (seq items)) :else (map #(map v-items %) (index-combinations n cnt)))))))
An alternative implementation I cam up with:
(defn subsets [n items]
(cond
(= n 0)
‘(())
(empty? items)
‘()
:default
(concat
(map #(cons (first items) %) (subsets (dec n) (rest items)))
(subsets n (rest items)))))
(defn permutations [items]
(let [n (count items)]
(if (= n 0)
(list ‘())
(loop [i (dec n)
result ‘()]
(if (>= i 0)
(recur
(dec i)
(concat
(map
#(cons (nth items i) %)
(permutations (concat (take i items) (drop (inc i) items))))
result))
result)))))
(defn combinations [n items]
(mapcat permutations (subsets n items)))