All subsets of a set in clojure

Question

I wish to generate all subsets of a set except empty set

ie

(all-subsets #{1 2 3}) => #{#{1},#{2},#{3},#{1,2},#{2,3},#{3,1},#{1,2,3}}

How can this be done in clojure?

Usually the powerset includes the empty set too. – Pointy Jan 04 '14 at 00:47 — Pointy, Jan 04 '14 at 00:47

score 12 · Answer 1 · answered Jan 03 '14 at 22:48

12

In your :dependencies in project.clj:

[org.clojure/math.combinatorics "0.0.7"]

At the REPL:

(require '[clojure.math.combinatorics :as combinatorics])

(->> #{1 2 3}
  (combinatorics/subsets)
  (remove empty?)
  (map set)
  (set))
;= #{#{1} #{2} #{3} #{1 2} #{1 3} #{2 3} #{1 2 3}}

clojure.math.combinatorics/subsets sensibly returns a seq of seqs, hence the extra transformations to match your desired output.

answered Jan 03 '14 at 22:48

Michał Marczyk

83,634
13
201
212

I'm hoping for a simple implementation and not rely on a library – zcaudate Jan 04 '14 at 07:02
6

@zcaudate: Clojure is a library language. A hand-written implementation to solve a general problem like this is never a good idea and simply not good practice, except for learning purposes. Relying on an official library like `math.combinatorics` has no trade-offs and usually outperforms everything you could do by hand by a far degree. Also you can expect it to be improved by people dedicated to the problem if improvements are possible. – Leon Grapenthin Jan 04 '14 at 15:38

Brent M. Spell · Answer 2 · 2014-10-16T20:54:30.760

5

Here's a concise, tail-recursive version with dependencies only on clojure.core.

(defn power [s]
   (loop [[f & r] (seq s) p '(())]
      (if f (recur r (concat p (map (partial cons f) p)))
            p)))

If you want the results in a set of sets, use the following.

(defn power-set [s] (set (map set (power s))))

edited Oct 16 '14 at 20:54

answered Oct 16 '14 at 20:04

Brent M. Spell

2,257
22
14

score 3 · Answer 3 · answered Jan 16 '14 at 00:57

@zcaudate: For completeness, here is a recursive implementation:

(defn subsets
  [s]
  (if (empty? s)
    #{#{}}
    (let [ts (subsets (rest s))]
      (->> ts
           (map #(conj % (first s)))
           (clojure.set/union ts)))))

;; (subsets #{1 2 3})

;; => #{#{} #{1} #{2} #{3} #{1 2} #{1 3} #{2 3} #{1 2 3}} (which is correct).

score 2 · Answer 4 · answered May 04 '15 at 15:02

This is a slight variation of @Brent M. Spell's solution in order to seek enlightenment on performance consideration in idiomatic Clojure.

I just wonder if having the construction of the subset in the loop instead of another iteration through (map set ...) would save some overhead, especially, when the set is very large?

(defn power [s]
    (set (loop [[f & r] (seq s) p '(#{})]
         (if f (recur r (concat p (map #(conj % f) p)))
             p))))

(power [1 2 3])
;; => #{#{} #{3} #{2} #{1} #{1 3 2} #{1 3} #{1 2} #{3 2}}

It seems to me loop and recuris not lazy. It would be nice to have a lazy evaluation version like Brent's, to keep the expression elegancy, while using laziness to achieve efficiency at the sametime.

This version as a framework has another advantage to easily support pruning of candidates for subsets, when there are too many subsets to compute. One can add the logic of pruning at position of conj. I used it to implement the prior algorithm for "Frequent Item Set".

score 1 · Accepted Answer · edited May 23 '17 at 12:34

1

refer to: Algorithm to return all combinations of k elements from n



(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))


(defn all-subsets [s]
  (apply concat
         (for [x (range 1 (inc (count s)))]
           (map #(into #{} %) (comb x s)))))

; (all-subsets #{1 2 3})
; (#{1} #{2} #{3} #{1 2} #{1 3} #{2 3} #{1 2 3})

edited May 23 '17 at 12:34

Community

1
1

answered Jan 04 '14 at 08:40

llj098

1,404
11
13

Probably the only real quibble I have with this answer is the use of ones and lower case L's as variable names. Had to squint a bit at it. – sleepysilverdoor Feb 24 '19 at 16:15

score 1 · Answer 6 · answered Feb 17 '16 at 20:09

This version is loosely modeled after the ES5 version on Rosetta Code. I know this question seems reasonably solved already... but here you go, anyways.

(fn [s]
  (reduce 
    (fn [a b] (clojure.set/union a 
      (set (map (fn [y] (clojure.set/union #{b} y)) a))))
#{#{}} s))

All subsets of a set in clojure

6 Answers6