闭律中的笛卡尔积
闭律中的笛卡尔积
提问于 2013-08-15 04:55:10
我正在尝试实现一个方法，它将获取一个列表列表，并返回这些列表的笛卡尔积。
到目前为止，我的情况如下：
(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))问题是我的解决方案真的是“手镯”。
(((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))但后来我遇到了这样的车祸：
((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和非常陌生，所以我可能走上了完全错误的轨道。请帮助！:)
回答 6
Stack Overflow用户
回答已采纳
发布于 2013-08-15 07:23:26
这比手工计算递归要容易得多：
(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)))Stack Overflow用户
发布于 2013-10-15 11:01:50
我会检查一下https://github.com/clojure/math.combinatorics
(combo/cartesian-积1 2) ;;=> ((1 3) (1 4) (2 3) (2 4))
Stack Overflow用户
发布于 2013-08-15 15:21:37
为了比较，本着原著的精神
(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))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18246549
复制相关文章
相似问题
腾讯云开发者
