CODEWITHSUNDEEP
clojure
dagda1
dagda1

Reputation: 28810

clojure - list all permutations of a list

Say I have a set like this:

#{"word1" "word2" "word3"}

How could I list all ways that these words might be ordered, i.e.

word1 word2 word3
word2 word3 word1
word3 word2 word1

etc.

Upvotes: 6

Views: 7489

Answers (2)

dagda1
dagda1

Reputation: 28810

Although math.combinatorics is probably the right answer, I was looking for something simpler to follow. Below is a non-lazy implementation that I can follow:

(defn permutations [colls]
  (if (= 1 (count colls))
    (list colls)
    (for [head colls
          tail (permutations (disj (set colls) head))]
      (cons head tail))))

Upvotes: 12

Diego Basch
Diego Basch

Reputation: 13079

The easiest way is using math.combinatorics:

user> (require '[clojure.math.combinatorics :as combo])
nil
user> (combo/permutations #{"word1" "word2" "word3"})
(("word1" "word2" "word3") ("word1" "word3" "word2") ("word2" "word1" "word3") ("word2" "word3"    "word1") ("word3" "word1" "word2") ("word3" "word2" "word1"))

Edit: I haven't looked at the math.combinatorics implementation, but here's a lazy version because OP asked for some code to follow.

(defn permutations [s]
  (lazy-seq
   (if (seq (rest s))
     (apply concat (for [x s]
                     (map #(cons x %) (permutations (remove #{x} s)))))
     [s])))

Upvotes: 17

Related Questions