CODEWITHSUNDEEP
clojuresetsubsetcombinatorics
zcaudate
zcaudate

Reputation: 14258

All subsets of a set in clojure

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?

Upvotes: 6

Views: 2744

Answers (6)

bazeblackwood
bazeblackwood

Reputation: 1204

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

Upvotes: 1

Yu Shen
Yu Shen

Reputation: 2910

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

Upvotes: 2

Brent M. Spell
Brent M. Spell

Reputation: 2257

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

Upvotes: 5

Leon Grapenthin
Leon Grapenthin

Reputation: 9266

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

Upvotes: 3

llj098
llj098

Reputation: 1412

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

Upvotes: 1

Michał Marczyk
Michał Marczyk

Reputation: 84331

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.

Upvotes: 14

Related Questions