99 Clojure Problems (23-26)

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)))))))