Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Last active March 19, 2021 03:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ericnormand/c2c94f698bf3ace64c5f722da6dec2fc to your computer and use it in GitHub Desktop.
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.

@steffan-westcott
Copy link

(defn sums-of-pairs [ns sum]
  (for [[x & ys] (take (count ns) (iterate rest ns))
        y ys
        :when (= sum (+ x y))]
    (sort [x y])))

@frankadrian314159
Copy link

frankadrian314159 commented Oct 26, 2020

"If clojure.math.combinatorics/combinations returned
duplicate combinations, all you'd need would be:

 (defn sums-of-pairs [seq tgt]
    (filter #(= tgt (apply + %)) (combinations seq 2)))

Sadly, clojure.math.combinatorics/multi-comb (which
supposedly returns combinations with duplicates) is
both private in the package and doesn't seem to work.

As such, you need to process the sequence yourself to
find combinations with duplicates."

(defn order-pair
(defn upper-triangular-products
  "Use clojure.math.combinatorics/cartesian-product to
  get all pairs of elements of seq, use partition to turn
  those into a matrix-like structure, and drop all lower-
  triangular and diagonal elements, leaving only the
  upper-triangular elements."
  [seq]
  (let [cnt (count seq)
        rng (range cnt)]
    (mapcat #(drop %1 %2)
            (map inc rng)
            (partition cnt
                       (cartesian-product seq seq)))))

(defn sums-of-pairs [seq tgt]
  (filter #(= tgt (apply + %))
          (upper-triangular-products seq)))

@KingCode
Copy link

KingCode commented Oct 26, 2020

(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))]
            (sort [x y]))))))

@steffan-westcott
Copy link

Shouldn't the third example in the problem statement include pair [2 5] as well?

Yes, I found the same when I tested my solution.

@nwjsmith
Copy link

(defn pairs
  [coll]
  (when-let [[x & xs] coll]
    (lazy-cat (for [y xs] [x y]) (pairs xs))))

(defn sum-of-pairs
  [numbers target]
  (filter #(= target (apply + %)) (pairs numbers)))

@zelark
Copy link

zelark commented Oct 26, 2020

(defn sums-of-pairs [numbers target]
  (let [len   (count numbers)
        pairs (for [x (range len), y (range (inc x) len)]
                [(nth numbers x) (nth numbers y)])]
    (->> pairs
         (filter #(== (apply + %) target))
         (map sort))))

(= (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]])

@miner
Copy link

miner commented Oct 26, 2020

(defn sums-of-pairs [coll sum]
  (let [vvv (vec (sort coll))
        cnt (count vvv)]
    (for [i (range cnt)
          j (range (inc i) cnt)
          :when (= sum (+ (vvv i) (vvv j)))]
      (vector (vvv i) (vvv j)))))

@ericnormand
Copy link
Author

Shouldn't the third example in the problem statement include pair [2 5] as well?

Yes! I fixed it. Thanks for catching that.

@sztamas
Copy link

sztamas commented Oct 26, 2020

Not the most compact, but O(N):

(defn sums-of-pairs
  ([coll target] (sums-of-pairs coll target {} []))
  ([coll target unpaired result]
   (if-not (seq coll)
     (vec result)
     (let [n      (first coll)
           match  (- target n)
           found? (unpaired match)]
       (recur
         (rest coll)
         target
         (if found?
           (dissoc unpaired n)
           (update unpaired n (fnil inc 0)))
         (if found?
           (concat result (->> [n match] sort vec (repeat (unpaired match))))
           result))))))

@zugnush
Copy link

zugnush commented Oct 26, 2020

(defn sums-of-pairs
  [nums target]
  (let [frq (frequencies nums)
        half (/ target 2)
        half-count (get frq half 0)]
    (apply concat
           (for [[k kcount] frq
                          :let [kpair (- target k)]
                          :when (<= k half)]
             (if (= k half)
               (when (< 1 half-count)
                 (repeat (quot half-count 2) [half half]))
               (repeat (min kcount (get frq kpair 0))  [k kpair]))))))

@mchampine
Copy link

If you don't output repeats, it's pretty clean:

(defn sums-of-pairs2 [ns sum]
  (->> (for [x ns y ns :when (and (not= x y) (= sum (+ x y)))]
         (vec (sort [x y]))) distinct vec))

Otherwise it gets messier. Here's an abomination:

(defn sums-of-pairs [ns sum]
  (let [rems (rest (iterate rest ns))
        mkprs #(map sort (map vector (repeat %) %2))
        prs (apply concat (map mkprs ns rems))]
    (vec (map vec (filter #(= sum (apply + %)) prs)))))

@treydavis
Copy link

(defn sums-of-pairs [nums sum]
  (->> (for [a (range (count nums)) b (range (count nums)) :when (not (= a b))] (sort [a b]))
       (distinct)          ;; n choose 2 combination indices
       (map #(map nums %)) ;; look up values at indices
       (filter (fn [[a b]] (= (+ a b) sum)))
       (map sort)))

@paulschun
Copy link

(defn- check-sums [collection target-number index]
  (let [[[cursor] sequence-to-check] (->> collection
                                          (drop index)
                                          (split-at 1))]
    (->> sequence-to-check
         (map (partial vector cursor))
         (filter #(= (apply + %) target-number))
         (map sort))))

(defn sums-of-pairs [collection target-number]
  (->> collection
       (count)
       (range)
       (map (partial check-sums collection target-number))
       (apply concat)))

@KingCode
Copy link

KingCode commented Oct 27, 2020

@mchampine you bring up an interesting point regarding duplicates, which made me reflect on the problem statement, and what constitutes a candidate pair (a pair to be tested for adding up to the target sum)
.
"Return all pairs found in the collection that sum up to the target number" : I wondered initially if an object can be paired with itself, but the first example shows otherwise as (4,4) is not part of the result but adds up to 8. So once an object is picked, pair it with all others but not itself.
However, input lists can have duplicates, and therefore a number could be paired with itself in some cases, e.g. if the first example had a duplicate 4, (4,4) would indeed be in the result.

Therefore when building the candidate pairs list from an input list that may have duplicates, the position in the list is the best (only?) way to differentiate two objects, not their value. For me, map-indexed came to the rescue to build the pairs: all objects having a different index are paired (once only, by constraining indexes in e.g. ascending order in a looping construct).

@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