随处插入程序 [英] Insert-everywhere procedure
问题描述
我正在尝试编写一个程序,该程序需要一个符号和一个列表,并将该符号插入给定列表内的每个可能位置(从而生成一个列表列表).我已经编码了以下定义,我必须实现这些定义:
I am trying to write a procedure that takes a a symbol and a list and inserts the symbol at every possible position inside the given list (thus generating a list of lists). I have coded the following definitions, which I must implement:
(define (insert-at pos elmt lst)
(if (empty? lst) (list elmt)
(if (= 1 pos)
(cons elmt lst)
(cons (first lst)
(insert-at (- pos 1) elmt (rest lst))))))
2
(define (generate-all-pos start end)
(if (= start end)
(list end)
(cons start (generate-all-pos (+ start 1) end))))
1在列表(数字),符号和列表本身中占据一个位置,并将符号插入到请求的位置. 2从头到尾定位一个目标位置(数字),并创建一个从头到尾带有数字的排序列表. 到目前为止,我已经知道了:
1 takes a position in a list (number), a symbol and the list itself and inserts the symbol at the requested position. 2 takes a start and a target position (numbers) and creates a sorted list with numbers from start to target. So far I have got this:
(define (insert-everywhere sym los)
(cond
[(empty? los) (list sym)]
[else (cons (insert-at (first (generate-all-pos (first los)
(first (foldl cons empty los)))) sym los) (insert-everywhere sym (rest los)))
]
)
)
会导致
> (insert-everywhere 'r '(1 2 3))
(list (list 'r 1 2 3) (list 2 'r 3) (list 3 'r) 'r)
所以我实际上设法移动了'r'.我对于保留列表中的先前成员感到困惑.也许我错过了一些非常简单的东西,但是我盯着代码看了很长时间,这是到目前为止我得到的最干净的结果.任何帮助将不胜感激.
so I actually managed to move the 'r' around. I'm kind of puzzled about preserving the preceding members of the list. Maybe I'm missing something very simple but I've stared and poked at the code for quite some time and this is the cleanest result I've had so far. Any help would be appreciated.
推荐答案
insert-everywhere
过程过于复杂,简单的map
就能解决问题.试试这个:
The insert-everywhere
procedure is overly complicated, a simple map
will do the trick. Try this:
(define (insert-everywhere sym los)
(map (lambda (i)
(insert-at i sym los))
(generate-all-pos 1 (add1 (length los)))))
Also notice that in Racket there exists a procedure called range
, so you don't need to implement your own generate-all-pos
:
(define (insert-everywhere sym los)
(map (lambda (i)
(insert-at i sym los))
(range 1 (+ 2 (length los)))))
无论哪种方式,它都能按预期工作:
Either way, it works as expected:
(insert-everywhere 'r '(1 2 3))
=> '((r 1 2 3) (1 r 2 3) (1 2 r 3) (1 2 3 r))
这篇关于随处插入程序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!