318 - PurelyFunctional.tv Newsletter - Puzzle - Combinations

00 Combinations.md

generate combinations

If I have 4 flowers to choose from (#{:rose :lily :daisy :tulip}), I can generate 4 different combinations of 3 flowers.

(#{:rose :lily :daisy}, #{:rose :lily :tulip}, #{:rose :daisy :tulip}, #{:lily 
:daisy :tulip})

Write a function combinations that takes a collection of values and a number of items to choose and generates all combinations of that size.

Example:

(defn combinations [coll n]
 ...)

(combinations #{:rose :lily :daisy :tulip} 3)
; => (#{:rose :lily :daisy}, #{:rose :lily :tulip}, #{:rose :daisy :tulip}, 
#{:lily :daisy :tulip})

Bonus points for clarity, interest, and efficiency.

Eric Normand.clj

(defn combinations' [r coll n]
  (cond
    (> n (count coll))
    nil

    (zero? n)
    nil

    (= 1 n)
    (map list coll)

    :else
    (let [x (first coll)
          xs (rest coll)]
      (lazy-cat
       ;; combinations with first element
       (map #(conj % x) (r r xs (dec n)))
       ;; combinations without first element
       (r r xs n)))))

(defn combinations [coll n]
  (let [f (memoize combinations')]
    (f f coll n)))

Mark Champine.clj

(defn combinations [n items]
  (cond
    (= n 0) #{#{}}
    (empty? items) #{}
    :else
    (concat (map
             #(clojure.set/union (hash-set (first items)) %)
             (combinations (dec n) (rest items)))
            (combinations n (rest items)))))

Steve Miner.clj

(defn combinations [coll n]
  (let [choose-indices (fn [cnt choose]
                        ;; {:pre [(pos-int? choose) (<= choose cnt)]}
                        (loop [i (dec choose) res (map vector (range cnt))]
                          (if (zero? i)
                            res
                            (recur (dec i)
                                   (mapcat (fn [prev] (map #(conj prev %)
                                                           (range (inc (peek prev)) cnt)))
                                           res)))))]
    (if-not (pos-int? n)
      (list ())
      (let [v (vec coll)
            cnt (count v)]
        (when (<= n cnt)
          (map #(into #{} (map v) %) (choose-indices cnt n)))))))

Trey Davis.clj

;; a last-minute submission

(defn nested-map-permutation [s]
  "Returns the permutations of the set as a nested map where each key is a choice."
  (apply hash-map (mapcat #(list % (foo (disj s %))) s)))

(defn nested-map-paths-seq [nested-map]
  "Returns every path in the nested map as a sequence of key-path vectors."
  (letfn [(children-at-path [path] (keys (get-in nested-map path)))]
    (rest (tree-seq
           (fn branch? [path] (not-empty (children-at-path path)))
           (fn children [path] (map #(conj path %) (children-at-path path)))
           []))))

(defn combinations [s n]
  (let [permutations (nested-map-paths-seq (nested-map-permutation s))
        permutations-of-size-n (filter #(= (count %) n) permutations)]
    (set (map #(set %) permutations-of-size-n))))