All partitions of a sequence, without recursion

partitions.clj

(ns partitions)

(defn nth-partition
  "Interpreting i as a binary sequence, split coll at every 1 in the sequence."
  [i coll]
  (loop [current [(first coll)]
         out []
         coll (next coll)
         i i]
    (if-not coll
      (conj out current)
      (let [head (first coll)
            i2 (int (/ i 2))]
        (case (mod i 2)
          0 (recur (conj current head)
                   out
                   (next coll)
                   i2)
          1 (recur [head]
                   (conj out current)
                   (next coll)
                   i2))))))

(defn partitions [coll]
  (let [n (dec (count coll))
        limit (Math/pow 2 n)]
    (for [i (range limit)]
      (nth-partition i coll))))

(comment
  (partitions [1 2 3])
  ;; ==> ([[1 2 3]]
  ;;      [[1] [2 3]]
  ;;      [[1 2] [3]]
  ;;      [[1] [2] [3]])
  (partitions [1 2 3 4])
  ;; ==> ([[1 2 3 4]]
  ;;      [[1] [2 3 4]]
  ;;      [[1 2] [3 4]]
  ;;      [[1] [2] [3 4]]
  ;;      [[1 2 3] [4]]
  ;;      [[1] [2 3] [4]]
  ;;      [[1 2] [3] [4]]
  ;;      [[1] [2] [3] [4]])
  )