clojure 中的笛卡尔积 [英] Cartesian product in clojure

问题描述

我正在尝试实现一种方法，该方法将获取列表列表并返回这些列表的笛卡尔积.

I'm trying to implement a method that will take a list of lists and return a the cartesian product of these lists.

这是我目前所拥有的:

(defn cart


([] '())
 ([l1] (map list l1))
 ([l1 l2] 
  (map 
    (fn f[x] (map
    (fn g [y] (list x y))
    l2))
      l1)
      )

)

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

 )





;test cases 
(println (cartesian-product '(a b) '(c d))) ; ((a c) (a d) (b c) (b d))
(println (cartesian-product ())) ;()
(println (cartesian-product '(0 1)))    ; ((0) (1))
(println (cartesian-product '(0 1) '(0 1))) ; ((0 0) (0 1) (1 0) (1 1))
(println (apply cartesian-product (take 4 (repeat (range 2))))) ;((0 0 0 0) (0 0 0 1) (0 0 1 0) (0 0 1 1) (0 1 0 0) (0 1 0 1) (0 1 1 0) (0 1 1 1) (1 0 0 0) (1 0 0 1) (1 0 1 0) (1 0 1 1) (1 1 0 0) (1 1 0 1) (1 1 1 0) (1 1 1 1))

问题是我的解决方案真的很支架".

The problem is my solution is really 'brackety'.

(((a c) (a d)) ((b c) (b d)))
()
(0 1)
(((0 0) (0 1)) ((1 0) (1 1)))
(((((((0 0) (0 1)) 0) (((0 0) (0 1)) 1)) 0) (((((0 0) (0 1)) 0) (((0 0) (0 1)) 1)) 1)) ((((((1 0) (1 1)) 0) (((1 0) (1 1)) 1)) 0) (((((1 0) (1 1)) 0) (((1 0) (1 1)) 1)) 1)))

我尝试添加

      (apply concat(reduce cart lists))

但后来我遇到了这样的崩溃:

but then I get a crash like so:

((a c) (a d) (b c) (b d))
()
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long clojure.lang.RT.seqFrom (RT.java:494)

所以，我想我很接近但遗漏了一些东西.然而，由于我对 clojure 和函数式编程非常陌生，所以我可能走上了完全错误的轨道.请帮忙！:)

So, I think I'm close but missing something. However since I'm so new to clojure and functional programming I could be on the completely wrong track. Please help! :)

推荐答案

这比手动计算递归要容易得多:

This is a lot easier to do as a for-comprehension than by trying to work out the recursion manually:

(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选择了.

The base case is obvious (it needs to be a list containing the empty list, not the empty list itself, since there is one way to take a cartesian product of no lists). In the recursive case, you just iterate over each element x of the first collection, and then over each cartesian product of the rest of the lists, prepending the x you've chosen.

请注意，以这种稍微不自然的顺序编写 for 推导式的两个子句很重要:交换它们会导致显着的减速.这样做的原因是为了避免重复工作.第二个绑定的主体将针对第一个绑定中的每个项目评估一次，这(如果您以错误的顺序编写子句)将意味着浪费了许多昂贵的递归子句的副本.如果你想格外小心，你可以明确这两个子句是独立的，而是写成:

Note that it's important to write the two clauses of the for comprehension in this slightly unnatural order: swapping them results in a substantial slowdown. The reason for this is to avoid duplicating work. The body of the second binding will be evaluated once for each item in the first binding, which (if you wrote the clauses in the wrong order) would mean many wasted copies of the expensive recursive clause. If you wish to be extra careful, you can make it clear that the two clauses are independent, by instead writing:

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

这篇关于clojure 中的笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！