clojure - ordered pairwise combination of 2 lists

Question

Being quite new to clojure I am still struggling with its functions. If I have 2 lists, say "1234" and "abcd" I need to make all possible ordered lists of length 4. Output I want to have is for length 4 is:

("1234" "123d" "12c4" "12cd" "1b34" "1b3d" "1bc4" "1bcd" 
 "a234" "a23d" "a2c4" "a2cd" "ab34" "ab3d" "abc4" "abcd")

which 2^n in number depending on the inputs.

I have written a the following function to generate by random walk a single string/list. The argument [par] would be something like ["1234" "abcd"]

(defn make-string [par] (let [c1 (first par) c2 (second par)] ;version 3 0.63 msec
  (apply str (for [loc (partition 2 (interleave c1 c2)) 
                   :let [ch (if (< (rand) 0.5) (first loc) (second loc))]] 
                     ch))))

The output will be 1 of the 16 ordered lists above. Each of the two input lists will always have equal length, say 2,3,4,5, up to say 2^38 or within available ram. In the above function I have tried to modify it to generate all ordered lists but failed. Hopefully someone can help me. Thanks.

Answer 1

Mikera is right that you need to use recursion, but you can do this while being both more concise and more general - why work with two strings, when you can work with N sequences?

(defn choices [colls]
  (if (every? seq colls)
    (for [item (map first colls)
          sub-choice (choices (map rest colls))]
      (cons item sub-choice))
    '(())))

(defn choose-strings [& strings]
  (for [chars (choices strings)]
    (apply str chars)))

user> (choose-strings "123" "abc")
("123" "12c" "1b3" "1bc" "a23" "a2c" "ab3" "abc")

This recursive nested-for is a very useful pattern for creating a sequence of paths through a "tree" of choices. Whether there's an actual tree, or the same choice repeated over and over, or (as here) a set of N choices that don't depend on the previous choices, this is a handy tool to have available.

Answer 2

You can also take advantage of the cartesian-product from the clojure.math.combinatorics package, although this requires some pre- and post-transformation of your data:

(ns your-namespace (:require clojure.math.combinatorics))

(defn str-combinations [s1 s2]
     (->>
        (map vector s1 s2) ; regroup into pairs of characters, indexwise
        (apply clojure.math.combinatorics/cartesian-product) ; generate combinations
        (map (partial apply str))))  ; glue seqs-of-chars back into strings

> (str-combinations "abc" "123")
("abc" "ab3" "a2c" "a23" "1bc" "1b3" "12c" "123")
>