Description
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