code challenge: combinatronics

[practicalli-johnny]

Given an array of integers, return the smallest set of indices of numbers such that they add up to a target number. You may not use the same element twice.

Examples: [1,2,6,3,17,82,23,234] -> 26 Solution [3,6] [1,2,6,3,17,82,23,234] -> 40 Solution [4,6] [1,2,6,3,17,82,23,234] -> 23 Solution [6]

So thus far only have the backbone of what I would want to do. So far have done sorting and filtering out the numbers that would be too high

(defn foo
  ([ls target] (let [new-ls (filter #(> target %)
                                    (sort ls))]
                 (foo (butlast new-ls) target (last new-ls))))
  ([ls target sum]     (list ls target sum)))

I was thinking a naive way to solve this would be to iterate through the remaining elements from the back. In the case of 1 2 3 4 5, would 5. So there's a path where you try 4+5, 3+5, 2+5, 1+5. And if it exceeds the target you ignore it. if it is lower, and there are still elements before that you iterate through those. I'm not really sure how I can express this with maps and perhaps making use of multi arity functions for recursionI just realised that I still need to make sure the solution is the smallest set possible .... Anyone has any thoughts or is Clojure not too great for such tasks? (edited)

It sounds like a combinatorics problem to me, at least for a brute force approach, so I'd reach for clojure.math.combinatorics and do something like this:

> clj -Sdeps '{:deps {org.clojure/math.combinatorics {:mvn/version "RELEASE"}}}'
user=> (require '[clojure.math.combinatorics :as c])
nil
user=> (defn small-pair [coll n]
         (->> (mapcat #(c/combinations coll (inc %)) (range (count coll)))
              (filter #(= n (reduce + %)))
              (sort-by count)
              (first)
              (map #(get (zipmap coll (range)) %))))
#'user/small-pair
user=> (small-pair [1,2,6,3,17,82,23,234] 26)
(3 6)
user=> (small-pair [1,2,6,3,17,82,23,234] 40)
(4 6)
user=> (small-pair [1,2,6,3,17,82,23,234] 23)
(6)
user=> 

(it would be more efficient to calculate the zipmap just once in a let at the top, but I was just playing in a REPL to get to this point). (edited)

I was thinking I needed to implement something like this https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ but in clojure Print all possible combinations of r elements in a given array of size n - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

Was gonna attempt to foolhardily reference the python code and make a conversion (if i had time)

The combinatorics library is great for stuff like this. Took me a few minutes to get that exact code above, but it really was just a dozen lines in the REPL looking at the shape of things as I worked from that top line down.

There's actually a function in there called subset that already does the mapcat.

This http://creditsuisse.recsolu.com/external/events/O4d5CSpiL25wEbLEAwcPkQ

Another approach:

(def data [1 2 6 3 17 82 23 234])

(defn recursive-comb
  [kset-index nset-index nset kset func]
  (if (neg? kset-index)
    (func kset)
    (doseq [i (range nset-index (- (dec (count nset)) kset-index))]
      (recursive-comb (dec kset-index) (inc i) nset (assoc kset kset-index (get nset i)) func))))(defn combinations
  [n k]
  (let [nset (vec (range (inc n)))
        kset (vec (repeat k 0))
        res (atom [])
        func #(swap! res conj %)]
    (recursive-comb (dec k) 0 nset kset func)
    @res))(defn all-combinations
  [n]
  (mapcat #(combinations n %)
          (range (inc n))))(defn smallest-pair
  [ints sum]
  (let [indices (all-combinations (count ints))]
    (reduce
     (fn[acc e]
       (if (= sum (reduce + (map #(get ints %) e)))
         (reduced e)
         nil))
     0 indices)))(smallest-pair data 26)

(smallest-pair data 40)

(smallest-pair data 23)

Credit mostly goes to this MATHLAB solution I adapted from: https://stackoverflow.com/a/35689122/172272

[didibus]

https://repl.it/@didibus/FindMinIndicesOfNumbersThatSumToN