372 - PurelyFunctional.tv Newsletter https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-372-model-change-over-time-with-state-machines/

00 subset sums.md

Subset sums

Write a function that takes a set of numbers and returns all subsets that sum to a given number. That's a mouthful. Here's an example.

;; subsets that sum to 6
(subset-sums #{1 2 3 4 5} 6) ;=> #{ #{1 5} #{2 4} }
;; subsets that sum to 7
(subset-sums #{1 2 3 5 6 7} 7) ;=> #{ #{1 6} #{2 5} #{7} }
;; subsets that sum to 0
(subset-sums #{0 1 -1} 0) ;=> #{ #{} #{0} #{1 -1} #{0 1 -1} }

Thanks to this site for the challenge idea.

Alan Thompson.clj

(ns tst.demo.core
  (:use tupelo.core tupelo.test)
  (:require
    [clojure.math.combinatorics :as combo]
    [schema.core :as s]
    [tupelo.schema :as tsk]))

(s/defn total :- s/Int
  [vals]
  (reduce + 0 (seq vals)))

(s/defn subset-sums :- #{#{s/Any}}
  [vals :- #{s/Int}
   tgt :- s/Int]
  (let [subsets (mapv set ; convert from list of lists => vector of sets
                  (combo/subsets (vec vals))) ; requires a vector input
        keepers (set ; result is a set of sets
                  (keep-if #(= tgt (total %)) subsets))]
    keepers))

(dotest
  (is= 0 (total [])) ; verify total function works for empty seqs
  (is= 1 (total [1]))
  (is= 3 (total [1 2]))
  (is= 6 (total [1 2 3]))

  (is= (subset-sums #{1 4 3 2 5} 6)
    #{#{1 5} #{4 2} #{1 3 2}})
  (is= (subset-sums #{7 1 6 3 2 5} 7)
    #{#{7} #{1 6} #{2 5}})
  (is= (subset-sums #{0 1 -1} 0)
    #{#{0 1 -1} #{} #{1 -1} #{0}})
  )

Clarice Bouwer.clj

(defn subset-sums
  [numbers sum]
  (letfn [(positives [coll]
            (filter #(not= 0 %) coll))

          (add [coll num-1]
            (map
             (fn [num-2]
               (if (= sum (+ num-1 num-2)) [num-1 num-2] 0))
             coll))

          (expand [numbers]
            (map
             (fn [num-1]
               (into #{}
                     (flatten
                      (positives
                       (add numbers num-1)))))
             numbers))]

    (filter #(not (empty? %)) (into #{} (expand numbers)))))


;; subsets that sum to 6
(subset-sums #{1 2 3 4 5} 6) ;=> #{#{3} #{1 5} #{4 2}}

;; subsets that sum to 7
(subset-sums #{1 2 3 5 6 7} 7) ;=> #{#{1 6} #{2 5}}

;; subsets that sum to 0
(subset-sums #{0 1 -1} 0) ;=> #{#{1 -1} #{0}}

Eric Honsey.clj

(ns subset-sum 
  (:require [clojure.test :refer [deftest is]]))

(defn subsets
  [s]
  (loop [[x & xs] s
         r #{#{}}]
    (if x
      (recur xs (concat r (map #(into #{} (cons x %)) r)))
      (drop-last r))))

(defn subset-sums
  [s target]
  (->> (subsets s)
       (filter #(= target (reduce + %)))
       (into #{})))

(deftest subset-sum-test
  (is (= #{#{1 5} #{2 4} #{1 2 3}} (subset-sums #{1 2 3 4 5} 6)))
  (is (= #{#{1 6} #{2 5} #{7}} (subset-sums #{1 2 3 5 6 7} 7)))
  (is (= #{#{} #{0} #{1 -1}} (subset-sums #{0 1 -1} 0))))

Eric Normand.clj

;; non-tail recursive is too slow, even with memoization
(defn subsets* [f s]
  (->> s
       (map #(f f (disj s %)))
       (reduce clojure.set/union #{s})))

(defn subsets [s]
  (subsets* (memoize subsets*) (set s)))

;; tail-recursive version is much faster
(defn subsets [s]
  (loop [ret #{#{}} rem s]
    (if (empty? rem)
      ret
      (let [[f & rst] rem]
        (recur (into ret (map #(conj % f)) ret) rst)))))

(defn subset-sums [s n]
  (->> s
       subsets
       (filter #(= n (reduce + 0 %)))
       set))

Gerrit Jansen van Vuuren.clj

(defn subset-sums [s ^long n] (->> s seq combo/subsets (map set) (filter #(= (reduce + %) n)) set))

Mark Champine.clj

(defn powerset [s]
  (if (empty? s) #{#{}}
      (clojure.set/union (powerset (next s))
        (map #(conj % (first s)) (powerset (next s))))))

(defn subset-sums [s n]
  (filter #(= n (reduce + %)) (powerset s)))

Viktor P.clj

(ns purelyfunctional-newsletters.issue-372
  (:require [clojure.test :refer :all]
            [clojure.string :as str]))

(defn subsets [cur-numbers other-numbers accept-fn]
  (loop [result (if (accept-fn cur-numbers) #{cur-numbers} #{})
         x      (first other-numbers)
         xs     (rest other-numbers)]
    (if (nil? x)
      result
      (let [other-results (subsets (conj cur-numbers x) xs accept-fn)]
        (recur (into other-results result)
               (first xs)
               (rest xs))))))

(defn subset-sums [xs target-sum]
  (subsets #{}
           xs
           (fn [input-numbers]
             (and
              (seq input-numbers)
              (= target-sum (apply + input-numbers))))))


(deftest subset-sums-testing
  (testing "basics"
    (are [x y] (= y x)
      (subset-sums #{} 0)           #{}
      (subset-sums #{0 1} 0)        #{#{0}}
      (subset-sums #{0 1} 1)        #{#{0 1} #{1}}
      (subset-sums #{0 1 2} 2)      #{#{0 2} #{2}}
      (subset-sums #{-1 1 -2 2} 0)  #{#{-1 1 -2 2} #{-1 1} #{-2 2}})
  (testing "examples"
    (are [x y] (= y x)
      (subset-sums #{1 2 3 4 5} 6)    #{#{1 5} #{4 2} #{1 3 2}}  
      (subset-sums #{1 2 3 5 6 7} 7)  #{#{7} #{1 6} #{2 5}}    
      (subset-sums #{0 1 -1} 0)       #{#{0 1 -1} #{1 -1} #{0}}))))

Here's my variation on Eric Normand's solution. It gains performance by using seqs for the intermediate subsets and deferring the creation of sets until needed.

(defn subset-sums [nums sum]
  (into #{} 
        (comp (filter #(zero? (reduce - sum %)))
              (map set))
        (reduce (fn [ss x] (into ss (map #(conj % x)) ss)) (list ()) nums)))