Find combinations of items in a nested collection

Question

It's a very typical problem that I come across here and there. Imagine that you have a collection of items of any type, and sometimes items are collections themselves; you then need to "expand" them and thus multiply the number of items in the result by number of items in that collection. An example would explain it better; consider input/output pairs:

[] -> [[]]
[1] -> [[1]]
[1 2 3 4 5] -> [[1 2 3 4 5]]
[[1 2] 3 4 5] -> [[1 3 4 5] [2 3 4 5]]
[[1 2] 3 [4 5]] -> [[1 3 4] [2 3 4] [1 3 5] [2 3 5]]

so, an entirely one-dimensional collection resolves into itself; a collection where some items are collections of M, N, O items result in a collection of order M×N×O.

The code I've come up with so far is this:

(defn smash [xs ys]
  (if-not (coll? ys)
    (map conj xs (repeat (count xs) ys))
    (mapcat #(smash xs %) ys)))

(defn extrusion [input]
  (loop [result [[]]
         xs input]
    (if (empty? xs)
      result
      (recur (smash result (first xs))
             (rest xs)))))

It gives me the result I need:

user=> (extrusion [])
[[]]
user=> (extrusion [1])
([1])
user=> (extrusion [1 2 3 4 5])
([1 2 3 4 5])
user=> (extrusion [[1 2] 3 4 5])
([1 3 4 5] [2 3 4 5])
user=> (extrusion [[1 2] 3 [4 5]])
([1 3 4] [2 3 4] [1 3 5] [2 3 5])

as well as it works for any number of layers.

Now, I have a very strong sensation that there is a way better solution; perhaps a function from clojure.combinatorics that I'm missing. I'm not talking about time-efficiency at this point, it's purely about lines of code.

If there's a shorter way to express this solution, I'd be super happy to know it. Thanks!

Answer 1

I'm going to admit right off the bat that I don't fully understand what this algorithm is supposed to do. I can make suggestions for extrusion though.

Note how in extrusion you're explicitly calling first and rest on xs once per iteration, then processing the head, and recursing on the tail. The more idiomatic way to split the head from the tail would be to use deconstruction. This also lets you get rid of the call to empty?:

(defn extrusion2 [input]
  (loop [result [[]]
         [x & xs] input] ; Split the "head" from the "tail"

    (if x ; x will be nil when the collection is empty
      (recur (smash result x) xs)
      result)))

I wouldn't use loop here at all though (even though I love loop). You're just iterating over a collection while maintaining an accumulator. This is a textbook case for reduce:

(defn extrusion3 [input]
  (reduce (fn [result x]
            (smash result x))
          [[]]  
          input))

Since you conveniently gave smash the same argument order as the required reducing function though, this can be simplified to:

(defn extrusion4 [input]
  (reduce smash [[]] input))

If you really wanted to ridiculous, since input is the last argument to reduce, you can just make the function a partial application of reduce:

(def extrusion5
  (partial reduce smash [[]]))