不使用 map 和 lambda 等函数的 Racket 中的排列列表
List of Permutations in Racket without using Functions like map and lambda
我无法编写与 map 和 lambda 功能相同的辅助函数
(define (permutations lst)
(cond [(empty? lst) '()]
[(empty? (rest lst)) (list lst)]
[else???]))
map
只是一个抽象。想象一下,你是一个典型的吃名单的人:
;; add 2 to each element
(define (add2 lst)
(if (null? lst)
'()
(cons (+ 2 (car lst))
(add2 (cdr lst)))))
(add2 '(1 2 3)) ; ==> (3 4 5)
;; reverse each sublist in a list
(define (revel lst)
(if (null? lst)
'()
(cons (reverse (car lst))
(revel (cdr lst)))))
(revel '((1 2) (3 4))) ; ==> ((2 1) (4 3))
你注意到这两者有多相似吗?这几乎是 90% 相同的代码。常用代码是map
的核心:
(define (map1 f lst)
(if (null? lst)
'()
(cons (f (car lst))
(map1 f (cdr lst)))))
现在我们可以使用 map1
来实现这两个
(define (add2 lst)
(map1 (lambda (v) (+ v 2)) lst))
(define (revel lst)
(map1 reverse lst))
当然 map
比 map1
多,因为它还支持更多的列表参数,但是实现完整的 map
超出了本 post 的范围。
所以这里有一种方法可以做到这一点。我假设你被允许编写辅助函数。
第一步是要意识到,在某些时候您将需要获取一个元素列表,然后 'thread' 通过它来生成所有可能的新列表,并将该元素插入某处。所以给定 (1 2)
和 3
你想要 ((3 1 2) (1 3 2) (1 2 3))
.
并且出于将变得清楚的原因,我将以函数 添加 其对某些先前存在的答案的方式来执行此操作。它本身将具有一些辅助功能。
(define (thread-list e l into)
;; Thread e through l accumulating into into
(thread-list-loop e '() l into))
(define (thread-list-loop e before after into)
;; Do the work of threading e through a list:
;; - before is the chunk of list before e;
;; - after is the chunk after e;
;; - into is what we're collecting into
(if (null? after)
;; We now just need before with e at the end
(cons (append before (list e)) into)
;; add the current thing to results and loop
(thread-list-loop
e
(append before (list (first after)))
(rest after)
(cons (append before (list e) after) into))))
让我们来测试一下:
> (thread-list 1 '(2 3) '())
'((2 3 1) (2 1 3) (1 2 3))
现在我们想要一个函数,它将接受一个元素和一组列表,然后将元素穿插在每个列表中,累加结果:
(define (thread-lists e lists into)
;; thread e through each element of lists, accumulating into into
(if (null? lists)
into
(thread-lists
e
(rest lists)
(thread-list e (first lists) into))))
并检查这个:
> (thread-lists 1 '((2 3) (3 2)) '())
'((3 2 1) (3 1 2) (1 3 2) (2 3 1) (2 1 3) (1 2 3))
我要到此为止,但是 看看上面的调用做了什么:给定 ((2 3) (3 2))
,这是 (2 3)
的排列, 和 1
, 它返回 (1 2 3)
的排列!所以你现在应该可以编写另一个函数 permutations
,它利用 thread-lists
来创建排列。
请注意,我不知道这种方法是否有效,我希望它不会。我认为这很清楚。
我无法编写与 map 和 lambda 功能相同的辅助函数
(define (permutations lst)
(cond [(empty? lst) '()]
[(empty? (rest lst)) (list lst)]
[else???]))
map
只是一个抽象。想象一下,你是一个典型的吃名单的人:
;; add 2 to each element
(define (add2 lst)
(if (null? lst)
'()
(cons (+ 2 (car lst))
(add2 (cdr lst)))))
(add2 '(1 2 3)) ; ==> (3 4 5)
;; reverse each sublist in a list
(define (revel lst)
(if (null? lst)
'()
(cons (reverse (car lst))
(revel (cdr lst)))))
(revel '((1 2) (3 4))) ; ==> ((2 1) (4 3))
你注意到这两者有多相似吗?这几乎是 90% 相同的代码。常用代码是map
的核心:
(define (map1 f lst)
(if (null? lst)
'()
(cons (f (car lst))
(map1 f (cdr lst)))))
现在我们可以使用 map1
(define (add2 lst)
(map1 (lambda (v) (+ v 2)) lst))
(define (revel lst)
(map1 reverse lst))
当然 map
比 map1
多,因为它还支持更多的列表参数,但是实现完整的 map
超出了本 post 的范围。
所以这里有一种方法可以做到这一点。我假设你被允许编写辅助函数。
第一步是要意识到,在某些时候您将需要获取一个元素列表,然后 'thread' 通过它来生成所有可能的新列表,并将该元素插入某处。所以给定 (1 2)
和 3
你想要 ((3 1 2) (1 3 2) (1 2 3))
.
并且出于将变得清楚的原因,我将以函数 添加 其对某些先前存在的答案的方式来执行此操作。它本身将具有一些辅助功能。
(define (thread-list e l into)
;; Thread e through l accumulating into into
(thread-list-loop e '() l into))
(define (thread-list-loop e before after into)
;; Do the work of threading e through a list:
;; - before is the chunk of list before e;
;; - after is the chunk after e;
;; - into is what we're collecting into
(if (null? after)
;; We now just need before with e at the end
(cons (append before (list e)) into)
;; add the current thing to results and loop
(thread-list-loop
e
(append before (list (first after)))
(rest after)
(cons (append before (list e) after) into))))
让我们来测试一下:
> (thread-list 1 '(2 3) '())
'((2 3 1) (2 1 3) (1 2 3))
现在我们想要一个函数,它将接受一个元素和一组列表,然后将元素穿插在每个列表中,累加结果:
(define (thread-lists e lists into)
;; thread e through each element of lists, accumulating into into
(if (null? lists)
into
(thread-lists
e
(rest lists)
(thread-list e (first lists) into))))
并检查这个:
> (thread-lists 1 '((2 3) (3 2)) '())
'((3 2 1) (3 1 2) (1 3 2) (2 3 1) (2 1 3) (1 2 3))
我要到此为止,但是 看看上面的调用做了什么:给定 ((2 3) (3 2))
,这是 (2 3)
的排列, 和 1
, 它返回 (1 2 3)
的排列!所以你现在应该可以编写另一个函数 permutations
,它利用 thread-lists
来创建排列。
请注意,我不知道这种方法是否有效,我希望它不会。我认为这很清楚。