笛卡儿产品在clojure [英] Cartesian product in clojure

问题描述

我想实现一个方法，它将获取列表的列表，并返回这些列表的笛卡尔乘积。

这里是我到目前为止：

  b 
 
 $ b（[]'）
（[l1]（map list l1））
（[l1 l2] 
 b（fn f [x]（map 
（fn g [y]（list xy））
 l2））
 l1）
）
 
 ）
 
（defn cartesian-product [& lists] 
（减少购物车列表）
 
）
 
 
 b 
 
 $ b;测试用例
（println（cartesian-product'（ab）'（cd））） （println（cartesian-product（）））;（）
（println（cartesian-product'（0 1）））; （（0）（1））
（println（cartesian-product'（0 1）'（0 1）））; （（0 0）（0 1）（10）（11））
（println（apply cartesian-product（take 4（repeat（range 2）））））;（（0 0 0 0） （0 0 1 1）（0 0 1 0）（0 0 1 0）（0 1 1 0）（0 1 0 0）（0 1 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））
  
 
 
 
问题是我的解决方案是真正的半价。
 code>（（ac）（ad））（（bc）（bd）））
（）
（0 1）
 ））（（0 0）（0 1））0）（（0 0）（0 1））1））0） （（（（0 0）（0 1））0）（（（0 0）（0 1））1） （1 0）（1 1））1））0）（（（（（10）（11））0） b  
我试过添加
 （apply concat（减少购物车列表））
  
但是我得到一个崩溃， 
 （（ac）（bc）（bd））
（）
 IllegalArgumentException Don不知道如何创建ISeq从：java.lang.Long clojure.lang.RT.seqFrom（RT.java:494）
  
所以，我想我很近，但缺少一些东西。然而，由于我是clojure和函数式编程的新手，我可以在完全错误的轨道。请帮忙！ ：）
解决方案
作为一个for-comprehension比尝试手动执行递归更容易： / p> 
 
 
 （defn cart [colls] 
（if（empty？colls）
' b $ b（for [x（first colls）
 more（cart（rest colls））] 
（cons x more））））
 
 user> （a 1黑）（a 2黑）（a 2黑）（a 3黑）（a 1黑）（a 1黑） 3白色）
（b 1黑色）（b 1白色）（b 2黑色）（b 2白色）（b 3黑色）（b 3白色）
 ）（c 2 black）（c 2 white）（c 3 black）（c 3 white））
  
基本情况是显而易见的（它需要是一个包含空列表的列表，而不是空列表本身，因为是以一种方式获取没有列表的笛卡尔乘积）。在递归的情况下，你只需遍历第一个集合的每个元素 x ，然后在其余列表的每个笛卡尔乘积之前加上 x 。
 
I'm trying to implement a method that will take a list of lists and return a the cartesian product of these lists. 

Here's what I have so far:
(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)))
I tried adding 
      (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)
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 [x (first colls)
          more (cart (rest 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))
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.

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