我需要在 Scheme lang的列表中的输入索引上切换 2 个元素。例如:
(交换索引 0 3 '(1 2 3 4 5))
(4 2 3 1 5)
有人可以帮忙吗?提前致谢!:)
现在我想不出一种方法来解决这个问题,除非在整个列表中迭代三遍,(每个一个list-ref
,一个多一个build-list
。)不是最有效的解决方案,但它是这样的:
(define (swap-index idx1 idx2 lst)
(define (build-list lst idx e1 e2)
(cond ((null? lst)
'())
((= idx idx1)
(cons e2 (build-list (cdr lst) (add1 idx) e1 e2)))
((= idx idx2)
(cons e1 (build-list (cdr lst) (add1 idx) e1 e2)))
(else
(cons (car lst) (build-list (cdr lst) (add1 idx) e1 e2)))))
(build-list lst 0 (list-ref lst idx1) (list-ref lst idx2)))
我假设给定列表的索引存在,否则list-ref
会产生错误。索引可以按任何顺序传递,这意味着:idx1
可以小于、等于或大于idx2
。它按预期工作,返回一个带有修改的新列表:
(swap-index 0 3 '(1 2 3 4 5))
=> '(4 2 3 1 5)
此方法最多遍历列表两次:
(define (swap-index index1 index2 lst)
;; FIND-ELEMENTS --
;; INPUT: count, an integer; lst, a list
;; OUTPUT: a pair of the form '(a . b)
(define (find-elements count lst)
(cond ((null? lst) '()) ; really, we should never reach this if indices are valid
((= count index1) ; found the first element, so hold on to it while we look for the next one
(cons (car lst) (find-elements (+ 1 count) (cdr lst))))
((= count index2) (car lst)) ; found the second element, return part 2 of the pair
(else ; since we only care about 2 elements we can just skip everything else
(find-elements (+ 1 count) (cdr lst)))))
;; BUILD-LIST --
;; INPUT: count, an integer; elements, a pair; lst, a list
;; OUTPUT: a new list
(define (build-list count elements lst)
(cond ((null? lst) '()) ; again, we shouldn't get here if indices are valid
((= count index1) ; reached first index, substitute 2nd element and keep going
(cons (cdr elements) (build-list (+ 1 count) elements (cdr lst))))
((= count index2) ; reached second index, substitute 1st element and stop
(cons (car elements) (cdr lst)))
(else ; everything else just gets added to the list per usual
(cons (car lst) (build-list (+ 1 count) elements (cdr lst))))))
(build-list 0 (find-elements 0 lst) lst)) ; call build-list using a call to find-elements as a parameter
首先,find-elements
查看列表并返回一cons
对我们想要交换的元素。 注意: 此代码取决于按顺序给出索引的假设,以便最小的在前。
接下来,build-list
获取输出,find-elements
以便在下一次遍历期间我们可以替换适当的元素。
这是clojure中的解决方案。我希望算法会有所帮助。
(defn split [idx lst]
(let [lst-rest (drop idx lst)]
[(take idx lst) (first lst-rest) (rest lst-rest)]))
(defn swap-index [idx1 idx2 lst]
(let [[lst1 e1 lst] (split idx1 lst)
[lst2 e2 lst3] (split (dec (- idx2 idx1)) lst)]
(concat lst1 [e2] lst2 [e1] lst3)))
=> (swap-index 0 3 [1 2 3 4 5])
(4 2 3 1 5)