Clojure - an ordered pair combination of 2 lists

Question

Being completely new to clojure, I am still struggling with my features. If I have 2 lists, say "1234" and "abcd", I need to make all possible ordered lists of length 4. The output I want is for length 4:

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

where 2 ^ n in the amount depending on the inputs.

I wrote the following function to randomly wander one line / list. The argument [par] will be similar to ["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 be of equal length, for example, 2,3,4,5, up to 2 ^ 38 or within the limits of the available plunger. In the function above, I tried changing it to create all ordered lists, but failed. Hope someone can help me. Thanks.

Answer 1

Mikera is right that you need to use recursion, but you can do it by being shorter and more general - why work with two lines 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 nesting is a very useful template for creating a sequence of paths through the "tree" of options. Whether there is an actual tree or the same choice is repeated over and over or (as here) a set of N options that are not dependent on previous options, this is a convenient tool for accessibility.

Answer 2

You can also use cartesian-product from the clojure.math.combinatorics package, although this requires some preliminary and subsequent conversion 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") > 

Answer 3

The trick is to make the function recursive by calling itself on the rest of the list at each step.

You can do something like:

 (defn make-all-strings [string1 string2] (if (empty? string1) [""] (let [char1 (first string1) char2 (first string2) following-strings (make-all-strings (next string1) (next string2))] (concat (map #(str char1 %) following-strings) (map #(str char2 %) following-strings))))) (make-all-strings "abc" "123") => ("abc" "ab3" "a2c" "a23" "1bc" "1b3" "12c" "123") 

Answer 4

 (defn combine-strings [ab] (if (seq a) (for [xs (combine-strings (rest a) (rest b)) x [(first a) (first b)]] (str x xs)) [""])) 

Now that I have written it, I understand that this is a less general version of the amaloy.

Answer 5

You can also use binary digits of numbers from 0 to 16 to form your combinations:
if the bit is zero, select from the first line otherwise the second.

eg. 6 = 2r0110 => "1bc4", 13 = 2r1101 => "ab3d", etc.

 (map (fn [n] (apply str (map #(%1 %2) (map vector "1234" "abcd") (map #(if (bit-test n %) 1 0) [3 2 1 0])))); binary digits (range 0 16)) => ("1234" "123d" "12c4" "12cd" "1b34" "1b3d" "1bc4" "1bcd" "a234" "a23d" "a2c4" "a2cd" "ab34" "ab3d" "abc4" "abcd") 

The same approach can be used to generate combinations of more than two lines.
Let's say you have 3 lines ("1234" "abcd" "ABCD"), there will be 81 combinations (3 ^ 4). Using three-digit digits of base-3:

 (defn ternary-digits [n] (reverse (map #(mod % 3) (take 4 (iterate #(quot % 3) n)))) (map (fn [n] (apply str (map #(%1 %2) (map vector "1234" "abcd" "ABCD") (ternary-digits n) (range 0 81)) 

Answer 6

 (def c1 "1234") (def c2 "abcd") (defn make-string [c1 c2] (map #(apply str %) (apply map vector (map (fn [col rep] (take (math/expt 2 (count c1)) (cycle (apply concat (map #(repeat rep %) col))))) (map vector c1 c2) (iterate #(* 2 %) 1))))) (make-string c1 c2) => ("1234" "a234" "1b34" "ab34" "12c4" "a2c4" "1bc4" "abc4" "123d" "a23d" "1b3d" "ab3d" "12cd" "a2cd" "1bcd" "abcd")