k-combinations.clj

(defn swap
  "Swap the elements at positions `i` and `j` in `v`."
  {:private true}
  [v i j]
  (-> v
      (assoc i (nth v j))
      (assoc j (nth v i))))

;; SEE: https://en.wikipedia.org/wiki/Heap%27s_algorithm
(defn permutations
  "Return a sequence of all the ways to arrange coll."
  [coll]
  (let [v (vec coll)
        n (count v)]
    (loop [n n
           a [v]]
      (if (zero? n)
        a
        (let [n* (dec n)
              a* (mapcat
                  (fn step [v]
                    (map
                     (fn [i]
                       (swap v i n*))
                     (range n)))
                  a)]
          (recur n* a*))))))


(defn k-combinations
  "All the ways to choose k items from coll."
  [coll k]
  (if (= k 1)
    (sequence (map vector) coll)
    (let [coll (vec coll)
          n (count coll)]
      (sequence
       (comp
        (reduce comp
                (repeat (dec k)
                        (mapcat
                         (fn [v]
                           (let [i (peek v)]
                             (map conj (repeat v) (range i)))))))
        (mapcat permutations)
        (map
         (fn [ptrs]
           (mapv nth (repeat coll) ptrs))))
       (map vector (range n))))))