Декартово произведение в clojure

Ответ 1

Это гораздо проще сделать для понимания, чем пытаться обработать рекурсию вручную:

(defn cart [colls]
  (if (empty? colls)
    '(())
    (for [more (cart (rest colls))
          x (first colls)]
      (cons x more))))

user> (cart '((a b c) (1 2 3) (black white)))
((a 1 black) (a 1 white) (a 2 black) (a 2 white) (a 3 black) (a 3 white) 
 (b 1 black) (b 1 white) (b 2 black) (b 2 white) (b 3 black) (b 3 white) 
 (c 1 black) (c 1 white) (c 2 black) (c 2 white) (c 3 black) (c 3 white))

Базовый случай очевиден (это должен быть список, содержащий пустой список, а не сам пустой список, поскольку есть один способ взять декартово произведение без списков). В рекурсивном случае вы просто перебираете каждый элемент x первого набора, а затем - каждый декартово произведение остальных списков, добавляя выбранный вами x.

Обратите внимание, что важно написать два предложения for понимания в этом немного неестественном порядке: их замена приводит к существенному замедлению. Причина этого состоит в том, чтобы избежать дублирования работы. Тело второй привязки будет оцениваться один раз для каждого элемента в первой привязке, что (если вы написали пункты в неправильном порядке) будет означать много потерянных копий дорогостоящего рекурсивного предложения. Если вы хотите быть особенно осторожным, вы можете дать понять, что эти два предложения независимы, вместо этого написав:

(let [c1 (first colls)]
  (for [more (cart (rest colls))
        x c1]
    (cons x more)))

Ответ 2

Я бы поставил https://github.com/clojure/math.combinatorics

(комбо/декартово-произведение [1 2] [3 4]) ;; = > ((1 3) (1 4) (2 3) (2 4))

Ответ 3

Для сравнения, в духе оригинала

(defn cart 
  ([xs] 
   xs) 
  ([xs ys] 
   (mapcat (fn [x] (map (fn [y] (list x y)) ys)) xs)) 
  ([xs ys & more] 
   (mapcat (fn [x] (map (fn [z] (cons x z)) (apply cart (cons ys more)))) xs)))

(cart '(a b c) '(d e f) '(g h i))
;=> ((a d g) (a d h) (a d i) (a e g) (a e h) (a e i) (a f g) (a f h) (a f i)
;    (b d g) (b d h) (b d i) (b e g) (b e h) (b e i) (b f g) (b f h) (b f i) 
;    (c d g) (c d h) (c d i) (c e g) (c e h) (c e i) (c f g) (c f h) (c f i))

Ответ 4

Я знаю, что опаздываю на вечеринку - я просто хотел добавить другой подход, для полноты картины.

По сравнению с подходом amalloy, он также ленив (списки параметров оцениваются с нетерпением) и немного быстрее, когда требуются все результаты (я протестировал их оба с помощью демонстрационного кода ниже), однако он склонен к переполнению стека (очень похоже на переполнение стека). основа for понимания, она генерирует и оценивает) по мере увеличения числа списков. Также помните, что eval имеет ограничение на размер кода, на который он может быть передан.

Рассмотрим сначала один случай проблемы: вы хотите найти декартово произведение [:a :b :c] и '(1 2 3). Очевидное решение состоит в том, чтобы использовать for понимания, как это:

(for [e1 [:a :b :c]
      e2 '(1 2 3)]
  (list e1 e2))

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3))

Теперь возникает вопрос: возможно ли обобщить это так, чтобы оно работало с произвольным числом списков? Ответ здесь утвердительный. Вот что делает следующий макрос:

(defmacro cart [& lists]
  (let [syms (for [_ lists] (gensym))]
    '(for [[email protected](mapcat list syms lists)]
       (list [email protected]))))

(macroexpand-1 '(cart [:a :b :c] '(1 2 3)))

; (clojure.core/for [G__4356 [:a :b :c] 
;                    G__4357 (quote (1 2 3))] 
;   (clojure.core/list G__4356 G__4357))

(cart [:a :b :c] '(1 2 3))

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3))

По сути, у вас есть компилятор генерировать соответствующий for понимания для вас. Преобразовать это в функцию довольно просто, но есть небольшая хитрость:

(defn cart [& lists]
  (let [syms (for [_ lists] (gensym))]
    (eval '(for [[email protected](mapcat #(list %1 ''~%2) syms lists)]
             (list [email protected])))))

(cart [:a :b :c] '(1 2 3))

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3))

Списки, оставленные без кавычек, обрабатываются как вызовы функций, поэтому здесь необходимо заключать в кавычки %2.

Демо онлайн:

; https://projecteuler.net/problem=205

(defn cart [& lists]
  (let [syms (for [_ lists] (gensym))]
    (eval '(for [[email protected](mapcat #(list %1 ''~%2) syms lists)]
             (list [email protected])))))

(defn project-euler-205 []

  (let [rolls (fn [n d]
                (->> (range 1 (inc d))
                  (repeat n)
                  (apply cart)
                  (map #(apply + %))
                  frequencies))

        peter-rolls (rolls 9 4)
        colin-rolls (rolls 6 6)

        all-results (* (apply + (vals peter-rolls))
                       (apply + (vals colin-rolls)))

        peter-wins (apply + (for [[pk pv] peter-rolls
                                  [ck cv] colin-rolls
                                  :when (> pk ck)]
                              (* pv cv)))]

    (/ peter-wins all-results)))

(println (project-euler-205)) ; 48679795/84934656

Ответ 5

Лично я использовал бы решение amalloy for. Мое общее правило заключается в том, что если мой цикл может быть выражен как одиночный map/filter/etc вызов с простым аргументом функции (поэтому имя функции или короткая форма fn/#()), то ее лучше для использования функции. Как только он становится более сложным, выражение for намного легче читать. В частности, for намного лучше, чем вложенные карты. Тем не менее, если бы я не использовал for здесь, вот как я напишу функцию:

(defn cart
  ([] '(()))
  ([xs & more]
    (mapcat #(map (partial cons %)
                  (apply cart more))
            xs)))

Что следует отметить: во-первых, нет необходимости в сокращении. Рекурсия может справиться с этим просто отлично.

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

В-третьих, как объясняет амалома, правильное значение (cart) равно '(()). Это на самом деле довольно тонко, и я надежно испортил это, когда пишу такую ​​функцию. Если вы тщательно проведете простой случай, вы сможете понять, почему это значение заставляет рекурсию работать.

В-четвертых, я вообще не люблю использовать fn. Это скорее личное предпочтение, но я всегда использую #(), partial или comp, если мне это удастся. #() определенно идиоматичен для меньших функций, хотя другие два немного реже.

В-пятых, некоторые заметки о стиле. Самая большая проблема - отступы. Лучшее предложение здесь - найти редактор, который автоматически присваивает код lisp. Автоотчерпывание - одна из самых важных вещей для вашего редактора, поскольку это делает ее ослепительно очевидной, когда ваши парнеры не совпадают. Кроме того, закрывающие парсеры никогда не ходят по своей линии, fn не нужны внутренние имена, если вы не планируете рекурсировать, и у меня обычно есть несколько новых строк, чем вы. Мне нравится думать, что мой код выше разумно прилично оформлен, и, как еще один пример, вот как я буду форматировать ваш код:

(defn cart
  ([] '())
  ([l1] (map list l1))
  ([l1 l2] 
    (map (fn [x]
           (map (fn [y]
                  (list x y))
                l2))
         l1)))

(defn cartesian-product [& lists] 
  (reduce cart lists))

Ответ 6

Для большинства целей ответ Алана велик, поскольку вы получаете ленивое понимание, и ленивый seq не вызовет переполнение стека, поскольку вы реализуете его члены, даже если вы не используете (recur).

Мне было интересно попробовать обработать хвостовую рекурсивную версию с явным recur, не в последнюю очередь из-за которой лень не будет иметь никакой помощи в моем приложении, но и для удовольствия и хихиканья:

(defn cartesian-product
  ([cols] (cartesian-product '([]) cols))
  ([samples cols]
    (if (empty? cols)
      samples
      (recur (mapcat #(for [item (first cols)]
                        (conj % item)) samples)
             (rest cols)))))