Sam*_*man 12 functional-programming clojure cartesian-product
我正在尝试实现一个方法,该方法将获取列表列表并返回这些列表的笛卡尔积.
这是我到目前为止所拥有的:
(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和函数式编程这么新,我可能会走上完全错误的轨道.请帮忙!:)
ama*_*loy 21
作为一种理解,这比通过手动计算递归更容易:
(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)))
为了比较,本着原创的精神
(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))
就个人而言，我会使用 amalloy 的for解决方案。我的一般经验法则是，如果我的循环可以用一个简单的函数参数（如函数名或短/形式）表示为单个map/ filter/etc 调用，则最好使用该函数。一旦它变得比这更复杂，表达式就会更容易阅读。尤其是远好于嵌套映射。也就是说，如果我不在这里使用，这就是我编写函数的方式：fn#()forforfor
(defn cart
([] '(()))
([xs & more]
(mapcat #(map (partial cons %)
(apply cart more))
xs)))
注意事项：首先，不需要reduce。递归可以很好地处理它。
第二，只有两种情况。我们可以在空列表上很好地调用该函数，因此我们只关心空列表与非空列表。
第三，作为amalloy解释的，正确的值(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))
我知道我迟到了 - 我只想添加一种不同的方法,为了完整起见.
与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 [~@(mapcat list syms lists)]
(list ~@syms))))
(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 [~@(mapcat #(list %1 `'~%2) syms lists)]
(list ~@syms)))))
(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 [~@(mapcat #(list %1 `'~%2) syms lists)]
(list ~@syms)))))
(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