Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
318 - PurelyFunctional.tv Newsletter - Puzzle - Combinations

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.

(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)))
(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)))))
(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)))))))
;; 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))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.