Skip to content

Instantly share code, notes, and snippets.

@tabidots
Created May 14, 2019 14:19
Show Gist options
  • Save tabidots/92c919293ce8d5ee82d203cb526d09e3 to your computer and use it in GitHub Desktop.
Save tabidots/92c919293ce8d5ee82d203cb526d09e3 to your computer and use it in GitHub Desktop.
Random product subset
(defn rand-approx-product-subset
"Generates a randomized subset of a coll of integers whose product has a chance of
approximating `goal`."
[goal coll]
(let [midrange (-> (apply max coll) (- (apply min coll)) (/ 2.0))
tipping-point (/ goal (Math/sqrt midrange))]
(loop [product 1N coll' (shuffle coll) subset []]
(if (> product tipping-point) subset
(let [x (first coll')]
(recur (*' product x) (rest coll') (conj subset x)))))))
(defn best-rand-approx-product-subset
"Repeatedly generates randomized subsets of a coll of integers, takes the first
`sample-size` subsets whose product is `goal` ± `precision`%, and returns the subset
among those that is closest to `goal`."
[goal coll sample-size precision]
(->> (repeatedly #(rand-approx-product-subset2 goal coll))
(keep #(let [ratio (/ (reduce *' 1.0 %) goal)]
(when (<= (- 1 precision) ratio (+ 1 precision))
{:error (abs (- 1 ratio)) :subset %})))
(take sample-size)
(apply min-key :error)
:subset))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment