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?

Answer 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})

Answer 2

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.

Answer 3

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))))

Answer 4

@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).

Answer 5

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".

Answer 6

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))