Skip to content
{{ message }}

Instantly share code, notes, and snippets.

ericnormand/00 Combinations.md

Last active Mar 24, 2019
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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 (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)))))))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ;; 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))))
to join this conversation on GitHub. Already have an account? Sign in to comment