任何人都可以将此代码转换为伪代码
任何人都可以将此代码转换为伪代码
提问于 2019-10-02 21:04:57
#lang racket
(define (cartesian-product . lists)
(foldr (lambda (xs ys)
(append-map (lambda (x)
(map (lambda (y)
(cons x y))
ys))
xs))
'(())
lists))
(cartesian-product '(1 2 3) '(5 6))我有球拍朗码，可以计算两个集合或列表的笛卡尔乘积，我不太理解这个代码，谁能把代码转换成伪代码。
回答 1
Stack Overflow用户
发布于 2019-10-02 22:46:22
该函数对应于笛卡尔积的this定义。
- The dot
.in the argument表示lists将收集所有参数(在一个列表中)，无论传入多少个参数。 - 如何调用这样的函数？使用
apply。它应用了一个使用列表中的项作为参数的函数：(apply f (list x-1 ... x-n)) = (f x-1 ... x-n) - foldr只是列表
上自然递归的抽象
; my-foldr : [X Y] [X Y -> Y] Y [List-of X] -> Y
; applies fun from right to left to each item in lx and base
(define (my-foldr combine base lx)
(cond [(empty? lx) base]
[else (combine (first lx) (my-foldr func base (rest lx)))]))应用1)、2)和3)中的简化，并将foldr中的“组合”函数转换为单独的辅助对象：
(define (cartesian-product2 . lists)
(cond [(empty? lists) '(())]
[else (combine-cartesian (first lists)
(apply cartesian-product2 (rest lists)))]))
(define (combine-cartesian fst cart-rst)
(append-map (lambda (x)
(map (lambda (y)
(cons x y))
cart-rst))
fst))
(cartesian-product2 '(1 2 3) '(5 6))让我们考虑一下combine-cartesian的作用:它只是将n元笛卡尔乘积转换为n元笛卡尔乘积。
我们想要：
(cartesian-product '(1 2) '(3 4) '(5 6))
; =
; '((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))我们有(first lists) = '(1 2)和递归调用的结果(归纳)：
(cartesian-product '(3 4) '(5 6))
; =
; '((3 5) (3 6) (4 5) (4 6))为了从我们拥有的(递归的结果)到我们想要的，我们需要在每个元素上加上cons 1，在每个元素上加上cons 2，并附加这些列表。概括一下，我们得到了使用嵌套循环的组合函数的更简单的重构：
(define (combine-cartesian fst cart)
(apply append
(for/list ([elem-fst fst])
(for/list ([elem-cart cart])
(cons elem-fst elem-cart)))))为了增加维度，我们将(first lists)的每个元素都归结到其余元素的笛卡尔乘积的每个元素上。
伪码：
cartesian product <- takes in 0 or more lists to compute the set of all
ordered pairs
- cartesian product of no list is a list containing an empty list.
- otherwise: take the cartesian product of all but one list
and add each element of that one list to every
element of the cartesian product and put all
those lists together.页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58202132
复制相关文章
相似问题
腾讯云开发者
