Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active March 19, 2021 03:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ericnormand/c2c94f698bf3ace64c5f722da6dec2fc to your computer and use it in GitHub Desktop.
401 - PurelyFunctional.tv Newsletter -

Sums of pairs

Write a function that takes a collection of numbers and a target number. Return all pairs of numbers found in the collection that sum up to the target number.

Examples

(sums-of-pairs [2 4 5 6] 8) ;=> [[2 6]]
(sums-of-pairs [3 2 0 1 1 5] 5) ;=> [[2 3] [0 5]]
(sums-of-pairs [1 3 2 3 4 5] 7) ;=> [[3 4] [3 4] [2 5]]

Notes

  • There can be duplicate numbers.
  • Each pair should be sorted.

Thanks to this site for the challenge idea where it is considered Expert level in JavaScript.

Please submit your solutions as comments on this gist.

@KingCode
Copy link

KingCode commented Oct 27, 2020

@sztamas Your O(n) idea is brilliant, what neat insight to use subtraction to find matches! I would only suggest handling the update to your unpaired map by only incrementing/adding, and not dissoc'ing any item, in order to benefit from duplicates.

Here is another O(n) version using your algorithm:

(defn sums-of-pairs [xs sum]
  (->> xs
       (reduce (fn [[pairs matches] x]
                 (let [y (- sum x)
                       ycount (get matches y 0)]
                   [(if (pos? ycount) 
                      (into pairs (repeat ycount (sort [x y])))
                       pairs), 
                    (update matches x (fnil inc 0))]))
               [[] {}])
       first))

@mchampine
Copy link

mchampine commented Oct 27, 2020

@KingCode Yes, the instruction "There can be duplicate numbers" is somewhat ambiguous, but I eventually decided that meant "in the input vector", and therefore the intent was to make 2-permutations of the input vector. But the then sorting the pairs added another level of strangeness. Kind of an odd set of requirements. Your idea to use map-indexed to create uniqueness was clever - I didn't think of that!

@sztamas
Copy link

sztamas commented Oct 27, 2020

Thanks @KingCode, but it wasn't an original idea, I must have seen that somewhere.
I do like your rewrite! 👍

It was dissoc'ing because it wasn't exactly clear to me what should happen when you have duplicates.
Example 3 makes it clear for the case when one number (3) in the pairs is duplicated, but what should happen if the other number (4) was duplicated too?

Duplicates weren't allowed in the original problem statement, so had no further examples to check.
Without duplicates all solutions are simpler, in the O(n) solution matches could be a set instead of map.

Also to note is that the original problem statement had an extra spin: they wanted the pairs in the order of "completes the cycle first" as they call it. ie. in example 3 they want:

[[3 4] [3 4] [2 5]] not [[3 4] [2 5] [3 4]]
because although 2 comes before the second 3, the pair of 3, 4 comes before the pair of 2 , 5, so the second [3 4] "completes" before [2 5].

That would make the "normal" 2 nested loops solutions incorrect, so you would have to do some extra work to take care of that.

@germ13
Copy link

germ13 commented Oct 27, 2020

;; create a (count coll) x (count coll) matrix with all possible pair sums from collection
;; restrict upper right matrix, this will omit commutative pair sums
;; omit diagonal to omit reflexive sums.
;; filter only pairs that sum to target and sort
(defn sum-of-pairs [coll target]
  (for [x (map-indexed vector coll)
        y (map-indexed vector coll)
        :when (and (< (first x) (first y)) 
                   (= (+ (second x) (second y)) target))] 
   (vec (sort [(second x) (second y)]))))

@michelemendel
Copy link

(defn gen-pairs-sub [[h & t]]
  (reduce #(conj %1 [h %2]) [] t))

(defn gen-pairs [xs acc]
  (if (empty? xs)
    acc
    (recur (rest xs) (concat acc (gen-pairs-sub xs)))))

(defn sums-of-pairs
  [xs n]
  (map sort (filter #(= n (+ (first %) (second %))) (gen-pairs xs []))))

@kthu
Copy link

kthu commented Oct 27, 2020

(defn sums-of-pairs
    [numbers target]
    (->> (loop [ns    numbers
                pairs []]
           (if (seq ns)
             (recur (rest ns)
                    (into pairs (mapv #(do [(first ns) %]) (rest ns))))
             pairs))
         (filter #(= (apply + %) target))
         (map sort)
         (mapv vec)))

@HughPowell
Copy link

Think I might have managed sufficient coverage with the properties this time. Mostly through hacking generators together.

(require '[clojure.test.check.clojure-test :refer [defspec]]
         '[clojure.test.check.properties :as check-properties]
         '[clojure.spec.alpha :as spec]
         '[clojure.spec.gen.alpha :as spec-gen])

(spec/def ::target int?)

(spec/def ::number-sequence (spec/coll-of int? :kind sequential? :min-count 2))

(defn sum-of-pairs
  "Find pairs that sum to target"
  [numbers target]
  (when (and (spec/valid? ::number-sequence numbers)
             (spec/valid? ::target target))
    (let [sorted-numbers (sort numbers)]
      (->> sorted-numbers
           (drop 1)
           (iterate #(drop 1 %))
           (mapcat (fn [x coll] (map #(vector x %) coll)) sorted-numbers)
           (filter (fn [[x y]] (try (= target (+ x y))
                                    (catch ArithmeticException _ false))))))))

(defspec empty-result-when-no-pairs-add-to-target
         100
  (check-properties/for-all [[target numbers] (spec-gen/bind
                                                (spec-gen/such-that
                                                  (fn [numbers] (try (inc (* 2 (apply max numbers)))
                                                                     (catch ArithmeticException _ false)))
                                                  (spec/gen ::number-sequence))
                                                (fn [numbers]
                                                  (spec-gen/return
                                                    (let [target (inc (* 2 (apply max numbers)))]
                                                      [target numbers]))))]
    (empty? (sum-of-pairs numbers target))))

(defn pair-generator [target]
  (spec-gen/fmap
    (fn [n] (map (juxt identity #(- target %)) n))
    (spec-gen/not-empty
      (spec-gen/vector
        (spec-gen/such-that
          (fn [n] (try (- target n)
                       (catch ArithmeticException _ false)))
          (spec/gen int?))))))

(def target-pairs-numbers-generator (spec-gen/bind
                                      (spec-gen/bind
                                        (spec/gen int?)
                                        (fn [target]
                                          (spec-gen/fmap
                                            (fn [pairs] [target pairs])
                                            (pair-generator target))))
                                      (fn [[target pairs]]
                                        (spec-gen/fmap
                                          (fn [numbers] [target pairs numbers])
                                          (spec-gen/shuffle (apply concat pairs))))))

(defspec every-result-sums-to-target
         100
  (check-properties/for-all [[target _pairs numbers] target-pairs-numbers-generator]
    (every? (fn [[x y]] (= target (+ x y))) (sum-of-pairs numbers target))))

(defspec every-result-is-ordered
         100
  (check-properties/for-all [[target _pairs numbers] target-pairs-numbers-generator]
    (every? (fn [[x y]] (<= x y)) (sum-of-pairs numbers target))))

(defspec every-generated-pair-is-in-the-output
         100
  (check-properties/for-all [[target pairs numbers] target-pairs-numbers-generator]
    (let [pair-frequencies (frequencies (map (comp vec sort) pairs))]
      (->> (sum-of-pairs numbers target)
           (reduce (fn [pair-frequencies' pair] (update pair-frequencies' pair dec)) pair-frequencies)
           vals
           (apply max)
           pos?
           not))))

@msladecek
Copy link

I wanted to use the (= target (+ a b)) relation to find the matching pairs rather than as a filter after generating the combinations.

Also, I'm making the additional assumption that a number can appear more than twice and each of the resulting pairs must appear in the result.

(defn factorial [num]
  (loop [n 2, fact 1]
    (if (<= n num)
      (recur (inc n) (* n fact))
      fact)))

(defn binomial-coefficient [n k]
  (/ (factorial n)
     (* (factorial k) (factorial (- n k)))))

(defn sums-of-pairs [nums target]
  (let [half-target (/ target 2)

        [smaller equal bigger]
        (reduce
         (fn [[smaller equal bigger] num]
           (case (compare num half-target)
             -1 [(conj smaller num) equal bigger]
              0 [smaller (conj equal num) bigger]
              1 [smaller equal (conj bigger num)]))
         [[] [] []]
         nums)

        complements (frequencies bigger)

        matched-complement
        (mapcat (fn [num]
                  (let [match (- target num)
                        match-count (get complements match 0)]
                    (repeat match-count [num match])))
                smaller)

        matched-self
        (repeat (binomial-coefficient (count equal) 2) [half-target half-target])]
    (vec (concat matched-complement matched-self))))

(sums-of-pairs [2 4 5 6] 8) ;=> [[2 6]]
(sums-of-pairs [3 2 0 1 1 5] 5) ;=> [[2 3] [0 5]]
(sums-of-pairs [1 3 2 3 4 5] 7) ;=> [[2 5] [3 4] [3 4]]

(sums-of-pairs [3 4 5] 8) ;=> [[3 5]]
(sums-of-pairs [3 4 4 5] 8) ;=> [[3 5] [4 4]]
(sums-of-pairs [3 4 4 4 5] 8) ;=> [[3 5] [4 4] [4 4] [4 4]]

Once I was done with this, I took a look back and realized that the problem statement can be mapped fairly cleanly to relational programming.

(require
 '[clojure.core.logic :as logic]
 '[clojure.core.logic.fd :as fd])

(defn sums-of-pairs [nums target]
  (logic/run* [a b]
    (logic/membero a nums)
    (logic/membero b nums)
    (fd/eq
     (< a b)
     (= target (+ a b)))))

(sums-of-pairs [2 4 5 6] 8) ;=> ([2 6])
(sums-of-pairs [3 2 0 1 1 5] 5) ;=> ([2 3] [0 5])
(sums-of-pairs [1 3 2 3 4 5] 7) ;=> ([3 4] [2 5] [3 4])

(sums-of-pairs [3 4 5] 8) ;=> ([3 5])
(sums-of-pairs [3 4 4 5] 8) ;=> ([3 5])
(sums-of-pairs [3 4 4 4 5] 8) ;=> ([3 5])

Note that this one ignores the (= a b) case. The easiest way to fix it that I can think of is to reuse matched-self from the previous snippet, but I left that out for now while I try to come up with a pure core.logic solution.
I'd appreciate any suggestions on how to do that.

@sztamas
Copy link

sztamas commented Oct 28, 2020

@msladecek, how about something like this?

(defn sums-of-pairs [nums target]
  (let [idxs+nums (map-indexed vector nums)]
    (mapv (comp vec sort)
          (logic/run* [a b]
            (logic/fresh [a-idx b-idx]
              (logic/membero [a-idx a] idxs+nums)
              (logic/membero [b-idx b] idxs+nums)
              (fd/eq
                (< a-idx b-idx)
                (= target (+ a b))))))))

Based on @KingCode's map-indexed idea above.

@msladecek
Copy link

@sztamas nice!

@KingCode
Copy link

KingCode commented Oct 30, 2020

@sztamas, I am interested by your core.logic version, and will study it (and @msladecek's too, I need to learn core.logic) - neat stuff! Regarding your mention earlier regarding the original requirements of outputting the pairs in order of "discovery", thanks for explaining that too! (The original author's explanation on the JS site made little sense to many including myself). I agree it is a nice add-on to make this even more interesting and as you said, the natural combinatorial pair generation approach runs counter to that requirement. For this constraint, a natural traversal one element at a time with look-back (efficiently or not), is the way to go, e.g as in a run-of-the-mill reduction:

(defn sums-of-pairs [xs sum]
  (->> xs
       (reduce (fn [[pairs seen] x]
                 [(into pairs
                        (for [y seen
                              :when (= sum (+ x y))]
                          (sort [x y]))),
                  (conj seen x)])
               [[] []])
       first))

Which may explain why your core.logic version on example 3 outputs [[3 4] [2 5] [3 4]], unless maybe a small tweak would fix it? I am curious to see if it would be feasible or easier without map-indexed? I know nothing about core.logic, so please feel free to correct me.

@sztamas
Copy link

sztamas commented Oct 30, 2020

@KingCode, I'm sorry if I gave the impression I'm a core.logic expert :).
I actually never used core.logic before, just found the problem posed by @msladecek's solution interesting enough to look into it a bit.

I'm not sure if your proposed solution is the only way to go.
The O(n) solution we co-edited above also outputs [[3 4] [3 4] [2 5]] for example 3, doesn't it?

And for the solutions based on map-indexed you could keep the indexes where you found the pairs and sort based on those.
Something along the lines of (when adapting your original solution):

(defn sums-of-pairs [xs sum]
  (->> xs (map-indexed vector)
       ((fn [ixs]
          (for [[i x] ixs
                [j y] ixs
                :when (< i j)
                :when (= sum (+ x y))]
            [[(max i j) i] (sort [x y])])))
       (sort-by first)
       (mapv second)))

For the core.logic solution I assume you could do the sorting similarly as a last step, but it might be possible to set it all up in core.logic.
I'm not sure, would have to check.

@vpetruchok
Copy link

(defn sums-of-pairs
  ([numbers target-number]) (sums-of-pairs numbers target-number [])

  ([numbers target-number acc]
   (if (empty? numbers)
     acc
     (let [[i & others] numbers
           res (for [j others :when (= target-number (+ i j))]
                 (vec (sort [i j])))
           acc' (into acc res)]
       (recur others target-number acc')))))

@KingCode
Copy link

KingCode commented Nov 1, 2020

@sztamas, nice rewrite! I love your arithmetic on the indexes, I wish I had thought of that :)

Yes indeed the previous solution with your O(n) alg. did pass the order test, and I was agreeing with you in my post, sorry about the confusion..

@proush42
Copy link

proush42 commented Nov 1, 2020

(defn sums-of-pairs [xs trg]
  (let [match? (fn [[a b]] (= trg (+ a b)))
        combos (for [i (range (count xs))
                     j (range (inc i) (count xs))]
                 [(nth xs i) (nth xs j)])]
    (->> (filter match? combos)
         (map sort))))

@Sinha-Ujjawal
Copy link

Sinha-Ujjawal commented Mar 19, 2021

Is it too late to answer? My solution to the problem-

(defn sums-of-pairs 
    [ns target] (first (reduce (fn [[l m] n]
                                   [(concat l (repeat (get m n 0) (sort [n (- target n)])))
                                    (update m (- target n) (fn [x] (if (= x nil) 1 (+ x 1))))]) [[] {}] ns)))
;; O(N) solution

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment