clojure - упорядоченная попарная комбинация из 2 списков

Question

Будучи совершенно новым для clojure, я все еще борюсь с его функциями.Если у меня есть 2 списка, скажем «1234» и «abcd», мне нужно составить все возможные упорядоченные списки длины 4. Вывод, который я хочу получить, для длины 4:

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

, что 2 ^ nчисло в зависимости от входных данных.

Я написал следующую функцию для случайного обхода одной строки / списка.Аргумент [par] будет что-то вроде ["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))))

Вывод будет 1 из 16 упорядоченных списков выше.Каждый из двух входных списков всегда будет иметь одинаковую длину, скажем, 2,3,4,5, вплоть до 2 ^ 38 или в пределах доступной памяти.В вышеупомянутой функции я попытался изменить это, чтобы генерировать все упорядоченные списки, но не удалось.Надеюсь, кто-нибудь сможет мне помочь.Спасибо.

Answer 1

Микера прав, что вам нужно использовать рекурсию, но вы можете сделать это, будучи одновременно более кратким и более общим - зачем работать с двумя строками, когда вы можете работать с N последовательностями?

(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")

Этот рекурсивный вложенный шаблон является очень полезным шаблоном для создания последовательности путей через «дерево» выбора.Независимо от того, есть ли фактическое дерево, или один и тот же выбор повторяется снова и снова, или (как здесь) набор из N вариантов, которые не зависят от предыдущих вариантов, это удобный инструмент для доступности.

Answer 2

Вы также можете воспользоваться cartesian-product из пакета clojure.math.combinatorics , хотя это требует некоторого предварительного и последующего преобразования ваших данных:

(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

Хитрость заключается в том, чтобы сделать функцию рекурсивной, вызывая себя в оставшейся части списка на каждом шаге.

Вы можете сделать что-то вроде:

(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 [a b]
  (if (seq a)
    (for [xs (combine-strings (rest a) (rest b))
          x [(first a) (first b)]]
      (str x xs))
    [""]))

Теперь, когда я написал это, я понимаю, что это менее универсальная версия Амальойи.

Answer 5

Вы также можете использовать двоичные цифры от 0 до 16 для формирования ваших комбинаций:
если бит равен нулю, выберите из первой строки в противном случае вторую.

например. 6 = 2r0110 => «1bc4», 13 = 2r1101 => «ab3d» и т. Д.

(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")

Тот же подход может применяться к генерации комбинаций из более чем 2 строк.
Допустим, у вас есть 3 строки («1234», «abcd», «ABCD»), будет 81 комбинация (3 ^ 4). Использование троичных цифр 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")